Concatenated Divisibility - Practice Coding Problems

Concatenated Divisibility - Problem

You are given an array of positive integers nums and a positive integer k.

A permutation of nums is said to form a divisible concatenation if, when you concatenate the decimal representations of the numbers in the order specified by the permutation, the resulting number is divisible by k.

Return the lexicographically smallest permutation (when considered as a list of integers) that forms a divisible concatenation. If no such permutation exists, return an empty list.

Input & Output

Example 1 — Basic Valid Case

$ Input: nums = [1,2,3], k = 6

› Output: [2,1,3]

💡 Note: Trying permutations: [1,2,3]→123 (not divisible), [1,3,2]→132 (not divisible), [2,1,3]→213 (not divisible), [2,3,1]→231 (not divisible), [3,1,2]→312 (312÷6=52, divisible!), [3,2,1]→321 (not divisible). Valid permutations are [3,1,2]. Lexicographically smallest is [3,1,2].

Example 2 — No Valid Solution

$ Input: nums = [1,2,5], k = 6

› Output: []

💡 Note: All possible concatenations: 125, 152, 215, 251, 512, 521. None are divisible by 6, so return empty array.

Example 3 — Single Element

$ Input: nums = [12], k = 4

› Output: [12]

💡 Note: Only one permutation possible: [12] → 12. Since 12 ÷ 4 = 3, it's divisible, so return [12].

Constraints

1 ≤ nums.length ≤ 12
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10³

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3] and divisor k=6

Process

Try different arrangements and check divisibility

Output

Return lexicographically smallest valid permutation

Key Takeaway

🎯 Key Insight: Use DP with bitmask to track remainder modulo k while building permutations, avoiding overflow and reducing complexity from O(n!) to O(n × 2ⁿ × k)

Asked in

G Google 15 M Microsoft 12 a Amazon 8 f Meta 6

The key insight is to use dynamic programming with bitmasks to track which numbers are used and the current remainder modulo k, avoiding expensive string concatenation and integer overflow. Best approach uses DP with O(n × 2ⁿ × k) time and O(2ⁿ × k) space.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(n × 2ⁿ × k)	O(2ⁿ × k)	Use DP with bitmask to track used numbers and current remainder modulo k
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all permutations and check divisibility, return lexicographically smallest valid one

Dynamic Programming with Bitmask — Algorithm Steps

Use bitmask to represent which numbers are used
Track remainder modulo k as we build the number
Use DP to avoid recomputing same states
Reconstruct lexicographically smallest valid permutation

Visualization

Tap to expand

Step-by-Step Walkthrough

Build DP Table

Track which bitmask+remainder combinations are achievable

Check Feasibility

Verify if full permutation with remainder 0 is possible

Reconstruct Solution

Build lexicographically smallest valid permutation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int compare(const void* a, const void* b) {
    int* ia = (int*)a;
    int* ib = (int*)b;
    return *ia - *ib;
}

int* solution(int* nums, int numsSize, int k, int* returnSize) {
    int n = numsSize;
    bool** dp = (bool**)malloc((1 << n) * sizeof(bool*));
    for (int i = 0; i < (1 << n); i++) {
        dp[i] = (bool*)calloc(k, sizeof(bool));
    }
    dp[0][0] = true;
    
    // Precompute powers of 10 modulo k
    int pow10[20];
    pow10[0] = 1;
    for (int i = 1; i < 20; i++) {
        pow10[i] = (pow10[i-1] * 10) % k;
    }
    
    // Fill DP table
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int rem = 0; rem < k; rem++) {
            if (!dp[mask][rem]) continue;
            
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) continue;
                
                char temp[20];
                sprintf(temp, "%d", nums[i]);
                int digits = strlen(temp);
                int newRem = (rem * pow10[digits] + nums[i]) % k;
                dp[mask | (1 << i)][newRem] = true;
            }
        }
    }
    
    // Check if solution exists
    if (!dp[(1 << n) - 1][0]) {
        *returnSize = 0;
        return NULL;
    }
    
    // Reconstruct solution
    int* result = (int*)malloc(n * sizeof(int));
    int mask = 0;
    int rem = 0;
    *returnSize = 0;
    
    for (int pos = 0; pos < n; pos++) {
        int candidates[10];
        int indices[10];
        int candCount = 0;
        
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                candidates[candCount] = nums[i];
                indices[candCount] = i;
                candCount++;
            }
        }
        
        // Sort candidates by value
        for (int i = 0; i < candCount - 1; i++) {
            for (int j = i + 1; j < candCount; j++) {
                if (candidates[i] > candidates[j]) {
                    int temp = candidates[i];
                    candidates[i] = candidates[j];
                    candidates[j] = temp;
                    temp = indices[i];
                    indices[i] = indices[j];
                    indices[j] = temp;
                }
            }
        }
        
        for (int c = 0; c < candCount; c++) {
            int num = candidates[c];
            int i = indices[c];
            char temp[20];
            sprintf(temp, "%d", num);
            int digits = strlen(temp);
            int newRem = (rem * pow10[digits] + num) % k;
            int newMask = mask | (1 << i);
            
            bool canComplete = false;
            if (pos == n - 1) {
                canComplete = (newRem == 0);
            } else {
                canComplete = dp[newMask][newRem];
            }
            
            if (canComplete) {
                result[(*returnSize)++] = num;
                mask = newMask;
                rem = newRem;
                break;
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < (1 << n); i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    int nums[10];
    int size = 0;
    int k;
    
    char line[100];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(nums, size, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ × k)

n positions, 2^n possible bitmasks, k possible remainders

✓ Linear Growth

Space Complexity

O(2ⁿ × k)

DP table stores states for each bitmask and remainder combination

✓ Linear Space

8.2K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler