3533. Concatenated Divisibility LeetCode Solution

Last updated: May 5, 2025

In this guide, you will get 3533. Concatenated Divisibility LeetCode Solution with the best time and space complexity. The solution to Concatenated Divisibility problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Concatenated Divisibility solution in C++
  4. Concatenated Divisibility solution in Java
  5. Concatenated Divisibility solution in Python
  6. Additional Resources
3533. Concatenated Divisibility LeetCode Solution image

Problem Statement of Concatenated Divisibility

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.

Example 1:

Input: nums = [3,12,45], k = 5
Output: [3,12,45]
Explanation:

Permutation
Concatenated Value
Divisible by 5

[3, 12, 45]
31245
Yes

[3, 45, 12]
34512
No

[12, 3, 45]
12345
Yes

[12, 45, 3]
12453
No

[45, 3, 12]
45312
No

[45, 12, 3]
45123
No

The lexicographically smallest permutation that forms a divisible concatenation is [3,12,45].

Example 2:

Input: nums = [10,5], k = 10
Output: [5,10]
Explanation:

Permutation
Concatenated Value
Divisible by 10

[5, 10]
510
Yes

[10, 5]
105
No

The lexicographically smallest permutation that forms a divisible concatenation is [5,10].

Example 3:

Input: nums = [1,2,3], k = 5
Output: []
Explanation:
Since no permutation of nums forms a valid divisible concatenation, return an empty list.

Constraints:

1 <= nums.length <= 13
1 <= nums[i] <= 105
1 <= k <= 100

Complexity Analysis

  • Time Complexity: O(2^n \cdot k \cdot n)
  • Space Complexity: O(2^n \cdot k)

3533. Concatenated Divisibility LeetCode Solution in C++

class Solution {
 public:
  vector<int> concatenatedDivisibility(vector<int>& nums, int k) {
    vector<int> lengths;
    vector<int> pows;

    ranges::sort(nums);

    for (const int num : nums) {
      lengths.push_back(to_string(num).length());
      pows.push_back(static_cast<int>(pow(10, lengths.back())) % k);
    }

    vector<vector<int>> mem(1 << nums.size(), vector<int>(k, -1));
    return dp(nums, pows, mem, k, 0, 0) ? reconstruct(nums, pows, mem, k, 0, 0)
                                        : vector<int>();
  }

 private:
  // Returns true if there is a way to form a number divisible by `k` using the
  // numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.
  bool dp(const vector<int>& nums, const vector<int>& pows,
          vector<vector<int>>& mem, int k, int mask, int mod) {
    if (mem[mask][mod] != -1)
      return mem[mask][mod] == 1;
    if (mask == (1 << nums.size()) - 1)
      return mod == 0;
    for (int i = 0; i < nums.size(); ++i)
      if ((mask >> i & 1) == 0) {
        const int newMod = (mod * pows[i] + nums[i]) % k;
        if (dp(nums, pows, mem, k, mask | 1 << i, newMod))
          return mem[mask][mod] = 1;
      }
    return mem[mask][mod] = 0;
  }

  // Reconstructs the numbers that form a number divisible by `k` using the
  // numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.
  vector<int> reconstruct(const vector<int>& nums, const vector<int>& pows,
                          vector<vector<int>>& mem, int k, int mask, int mod) {
    for (int i = 0; i < nums.size(); ++i)
      if ((mask >> i & 1) == 0) {
        const int newMod = (mod * pows[i] + nums[i]) % k;
        if (dp(nums, pows, mem, k, mask | 1 << i, newMod)) {
          vector<int> res{nums[i]};
          vector<int> rest =
              reconstruct(nums, pows, mem, k, mask | 1 << i, newMod);
          ranges::copy(rest, ranges::back_inserter(res));
          return res;
        }
      }
    return {};
  }
};
/* code provided by PROGIEZ */

3533. Concatenated Divisibility LeetCode Solution in Java

class Solution {
  public int[] concatenatedDivisibility(int[] nums, int k) {
    final int n = nums.length;
    int[] lengths = new int[n];
    int[] pows = new int[n];

    Arrays.sort(nums);

    for (int i = 0; i < n; ++i) {
      lengths[i] = String.valueOf(nums[i]).length();
      pows[i] = (int) Math.pow(10, lengths[i]) % k;
    }

    Integer[][] mem = new Integer[1 << n][k];
    return dp(nums, pows, mem, k, 0, 0) ? reconstruct(nums, pows, mem, k, 0, 0) : new int[0];
  }

  // Returns true if there is a way to form a number divisible by `k` using the
  // numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.
  private boolean dp(int[] nums, int[] pows, Integer[][] mem, int k, int mask, int mod) {
    if (mem[mask][mod] != null)
      return mem[mask][mod] == 1;
    if (mask == (1 << nums.length) - 1)
      return (mem[mask][mod] = mod == 0 ? 1 : 0) == 1;
    for (int i = 0; i < nums.length; ++i)
      if ((mask >> i & 1) == 0) {
        final int newMod = (mod * pows[i] + nums[i]) % k;
        if (dp(nums, pows, mem, k, mask | 1 << i, newMod))
          return (mem[mask][mod] = 1) == 1;
      }
    return (mem[mask][mod] = 0) == 1;
  }

  // Reconstructs the numbers that form a number divisible by `k` using the
  // numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.
  private int[] reconstruct(int[] nums, int[] pows, Integer[][] mem, int k, int mask, int mod) {
    for (int i = 0; i < nums.length; ++i)
      if ((mask >> i & 1) == 0) {
        final int newMod = (mod * pows[i] + nums[i]) % k;
        if (dp(nums, pows, mem, k, mask | 1 << i, newMod)) {
          int[] first = new int[] {nums[i]};
          int[] rest = reconstruct(nums, pows, mem, k, mask | 1 << i, newMod);
          int[] res = new int[first.length + rest.length];
          System.arraycopy(first, 0, res, 0, first.length);
          System.arraycopy(rest, 0, res, first.length, rest.length);
          return res;
        }
      }
    return new int[0];
  }
}
// code provided by PROGIEZ

3533. Concatenated Divisibility LeetCode Solution in Python

class Solution:
  def concatenatedDivisibility(self, nums: list[int], k: int) -> list[int]:
    n = len(nums)
    nums.sort()
    lengths = [len(str(num)) for num in nums]
    pows = [pow(10, length, k) for length in lengths]

    @functools.lru_cache(None)
    def dp(mask: int, mod: int) -> bool:
      """
      Returns True if there is a way to form a number divisible by `k` using the
      numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.
      """
      if mask == (1 << n) - 1:
        return mod == 0
      for i in range(n):
        if (mask >> i & 1) == 0:
          newMod = (mod * pows[i] + nums[i]) % k
          if dp(mask | 1 << i, newMod):
            return True
      return False

    def reconstruct(mask: int, mod: int) -> list[int]:
      """
      Reconstructs the numbers that form a number divisible by `k` using the
      numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.
      """
      for i in range(n):
        if (mask >> i & 1) == 0:
          newMod = (mod * pows[i] + nums[i]) % k
          if dp(mask | 1 << i, newMod):
            return [nums[i]] + reconstruct(mask | 1 << i, newMod)
      return []

    return reconstruct(0, 0) if dp(0, 0) else []
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.