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.
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.
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.
Therefore the answer is (d – 1) * (d^(N – 1)) if A[] contains 0 else d^N.
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[].
Let First(i) be the number formed by taking the first i digits of it.
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];
}
}Last updated