Count of integers of length N and value less than K such that they contain digits only from the set

Given a set of digits A[] in sorted order and two integers N and K, the task is to find how many numbers of length N are possible whose value is less than K and the digits are from the given set only.

Note: that you can use the same digit multiple times.

Examples:

Input: A[] = {0, 1, 5}, N = 1, K = 2 Output: 2 Only valid numbers are 0 and 1.

Input: A[] = {0, 1, 2, 5}, N = 2, K = 21 Output: 5 10, 11, 12, 15 and 20 are the valid numbers.

Approach:

Let d be the size of A[]. We can break this problem into three simpler cases.

1. When N is greater than the length of K, It is obvious that if the length of N is greater than the length of k or if d is equal to 0, no such number is possible.

2. When N is smaller than the length of K, then all possible combinations of digit of length N are valid. Also, we have to keep in mind that 0 can’t be in the first place. So, if A[] contains 0, the first place can be filled in (d – 1) ways. Since repetition is allowed and 0 can occupy the other places, rest N – 1 places can be filled in d * d * … * d(N – 1) times i.e. in d^(N-1) ways.

3. Therefore the answer is (d – 1) * (d^(N – 1)) if A[] contains 0 else d^N.

4. When N is equal to the length of K, this is the trickiest part. We need to use Dynamic Programming for this part. Construct a digit array of K. Let’s call it digit[].

5. Let First(i) be the number formed by taking the first i digits of it.

6. Let lower[i] denote the number of elements in A[] which are smaller than i.

For example, First(2) of 423 is 42. If A[] = {0, 2} then lower[0] = 0, lower[1] = 1, lower[2] = 1, lower[3] = 2. Generate N digit numbers by dynamic programming.

Let dp[i] denote total numbers of length i which are less than first i digits of K. Elements in dp[i] can be generated by two cases:

• For all the numbers whose First(i – 1) is less than First(i – 1) of K, we can put any digit at ith index. Hence, dp[i] = dp[i] + (dp[i – 1] * d)

• For all the numbers whose First(i – 1) is the same as First(i – 1) of K, we can only put those digits which are smaller than digit[i]. Hence, dp[i] = dp[i] + lower[digit[i]].

Finally we return dp[N].

Note: For the first index don’t include 0 if N is not 1 and dp[0]=0.

public class Solution {
    public int[] convertToArray(int t) {
        ArrayList<Integer> ans = new ArrayList<>();
        while (t > 0) {
            ans.add(t % 10);
            t /= 10;
        }
        // If the original number was -> "0"
        if (ans.size() == 0)
            ans.add(0);
        int[] number = new int[ans.size()];
        // Reverse the array
        for (int i = ans.size() - 1; i >= 0; i--)
            number[ans.size() - (i + 1)] = ans.get(i);
        return number;
    }

    public int solve(int[] set, int N, int Target) {
        int size = set.length;
        int[] number = convertToArray(Target);
        int targetSize = number.length;
        // If we need to create a number whose length > target's length
        // then it is not possible
        if (size == 0 || N > targetSize)
            return 0;
        if (N < targetSize) {
            // If 0 is present in the set, then we cannot put it at first position
            if (set[0] == 0 && N != 1)
                return (size - 1) * (int) Math.pow(size, N - 1);
            else
                return (int) Math.pow(size, N);
        }
        // At this point N == target Size
        // dp[i] denote total numbers of length i which are less than first i digits of
        // "Target"
        int[] dp = new int[N + 1];
        // lower[i] denote the number of elements in "set" which are smaller than i
        int[] lower = new int[11];
        for (int x : set)
            lower[x + 1] = 1;
        for (int i = 1; i <= 10; i++)
            lower[i] += lower[i - 1];
        boolean flag = true;
        for (int i = 1; i <= N; i++) {
            int smallerDigits = lower[number[i - 1]];
            dp[i] = dp[i - 1] * size;
            // For first index we can't use 0
            if (i == 1 && set[0] == 0 && N != 1)
                smallerDigits -= 1;
            // If there is a set present, which can form 
            // exact digits upto this point
            if (flag)
                dp[i] += smallerDigits;
            // Is ith digit of "Target", present in the set
            flag = flag && (lower[number[i - 1] + 1] == lower[number[i - 1]] + 1);
        }
        return dp[N];
    }
}