Concatenated Divisibility

Hard

Asked by:

4 views

Topics:

ArraysRecursionDynamic ProgrammingGreedy Algorithms

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] <= 10⁵
1 <= k <= 100

Try coding it in LeetCode

Concatenated Divisibility

Hard

Asked by:

4 views

Topics:

ArraysRecursionDynamic ProgrammingGreedy Algorithms

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] <= 10⁵
1 <= k <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible value ranges for the numbers in the input array? Could they be negative or zero?
If no two numbers concatenate to form a number divisible by k, what should the function return?
Can the input array be empty or contain only one element?
Does the order of concatenation matter? That is, should I consider both 'a' concatenated with 'b' and 'b' concatenated with 'a'?
Is k guaranteed to be a positive integer?

Brute Force Solution

Approach

We are trying to find if a set of numbers, when combined in a particular order, create a number that is divisible by another given number. The brute force method involves trying every possible combination of these numbers to see if any of them meet the divisibility requirement.

Here's how the algorithm would work step-by-step:

Take all the numbers you're given.
Arrange these numbers in every possible order.
For each arrangement, combine the numbers into a single, large number by placing them next to each other.
Check if this large number is divisible by the given divisor.
If it is divisible, you've found a solution; otherwise, try the next arrangement.
Continue until you've checked all possible arrangements or found a successful combination.

Code Implementation

import itertools

def concatenated_divisibility_brute_force(numbers, divisor):
    # Generate all possible permutations of the numbers.
    for permutation in itertools.permutations(numbers):

        # Construct the concatenated number from the current permutation.
        concatenated_number_string = "".join(map(str, permutation))
        concatenated_number = int(concatenated_number_string)

        # Check if the concatenated number is divisible by the divisor.
        if concatenated_number % divisor == 0:
            return True

    # If no permutation yields a divisible number, return False.
    return False

Big(O) Analysis

Time Complexity

O(n! * k) – The algorithm generates all permutations of the input array of size n. Generating all permutations takes O(n!) time. For each permutation, the algorithm concatenates the numbers, which takes O(k) time where k is the total number of digits across all numbers, and then checks for divisibility. Therefore, the overall time complexity is O(n! * k).

Space Complexity

O(N) – The algorithm generates all permutations of the input numbers. To achieve this, a common approach involves recursion, leading to a call stack. The maximum depth of the call stack corresponds to the number of input numbers, N, as each level explores a new ordering. Furthermore, a temporary list to hold the current permutation being built may be required, which again has size N. Therefore, the auxiliary space complexity is O(N), dominated by the recursion depth and temporary list.

Optimal Solution

Approach

The problem requires checking if concatenating numbers in a given list in some order creates a number divisible by a target number. The clever approach significantly reduces computation by using remainders to avoid dealing with huge concatenated numbers directly.

Here's how the algorithm would work step-by-step:

Recognize that we don't need to actually build huge numbers by concatenating. We only care about whether the final result is divisible by a given number.
Figure out the remainder each number gives when divided by the given number. Store these remainders.
When you put two numbers together, you can calculate the new remainder without making the combined number. The key is to multiply the remainder of the first number by a power of 10 (based on the number of digits of the second number), add the remainder of the second number and then find remainder after dividing this result by the target number.
Try different orders of numbers, keeping track of the running remainder. Use a technique called dynamic programming to avoid re-calculating remainder for overlapping sequences of numbers.
If, at any point, the running remainder is zero, it means we've found an order that works, and we can stop. Otherwise, keep searching through the order possibilities.
Using the remainders and smart order explorations saves lots of calculation time and memory, which allows for efficiently solving the problem.

Code Implementation

def concatenated_divisibility(number_list, divisor):
    number_of_numbers = len(number_list)

    remainders = [number % divisor for number in number_list]

    # dp[mask] stores the remainder when concatenating a subset of numbers
    dp = {0: 0}

    for mask in range(1, 2**number_of_numbers):
        for i in range(number_of_numbers):
            if (mask >> i) & 1:

                previous_mask = mask ^ (1 << i)

                #Ensure there is a value already computed in the 'dp' dictionary
                if previous_mask in dp:
                    number_of_digits = len(str(number_list[i]))
                    power_of_ten = pow(10, number_of_digits, divisor)

                    # Calculate remainder using the previous remainder and current number.
                    current_remainder = (dp[previous_mask] * power_of_ten + remainders[i]) % divisor
                    dp[mask] = current_remainder

                    # If the remainder is 0, we found a solution.
                    if current_remainder == 0:
                        return True
                    break
    return False

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores different orders (permutations) of the n numbers. Generating all permutations of n elements takes O(n!) time. While dynamic programming is used to optimize the calculation of remainders for sub-sequences, the fundamental task of iterating through possible orderings dominates the computational complexity. Therefore, the overall time complexity is dictated by the permutation generation.

Space Complexity

O(N * 2^N) – The primary driver of auxiliary space is the dynamic programming technique used to store the remainders for overlapping sequences of numbers. This involves storing remainders for each possible subset of the input list, leading to 2^N possible subsets. For each subset, we also need to store the remainder calculated so far, and at most N numbers each can be picked to create the subset so it would be N * 2^N. Therefore, the space complexity is O(N * 2^N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list or appropriate error value as no concatenation is possible.
Input array with only one element	Return an empty list or appropriate error value since concatenation requires at least two elements.
Input array contains zero	Handle zero appropriately during concatenation, ensuring no division by zero errors if the target uses the concatenated string as the divisor.
Input array contains negative numbers	Concatenation should handle negative numbers correctly, preserving the sign.
Large numbers leading to integer overflow during concatenation	Use long or appropriate data type to prevent overflow and consider potential issues with target value exceeding allowed limits.
All numbers in the array are identical	Ensure that pairs of identical numbers are correctly identified and included in the result if the concatenated result is divisible.
No valid pair exists in the input array	Return an empty list or an appropriate error indicator if no concatenated pair satisfies the divisibility requirement.
Target number is zero	Avoid division by zero by handling this case appropriately, possibly by returning empty list or throwing exception.