You should decompose your problem.
Global algorithm
IMO, you should start at n = 0
, and go up. For each value of n
, check if the sequence of digits needed to represent it is allowed. As soon as you can't, n
is your answer.
Smaller part
The new problem is to verify if the sequence of digits for a given number is allowed. That does not seem very difficult. You seem to deal with base 10 numbers only I guess:
- decompose your number in base 10 digits
- count the number of occurrences of each digit in your number
- compare with the quantity available of that digit
- if there are not enough, you're done, the number can't be represented
- if there are enough, keep going with the other digits
Example implementation of the main algo. The argument nbAllowed
would be a 10-sized array containing the quantity available of each digit. Ex: nbAllowed[2]
is the number of times that the digit '2' is allowed to be used.
public static int smallestNonRepresentable(int[] nbAllowed) {
int n=0;
while (isRepresentable(n, nbAllowed)) {
n++;
}
return n;
}
Example implementation of the subroutine. This methods returns whether n
is representable depending on the quantity available for each digit.
private static boolean isRepresentable(int n, int[] nbAllowed) {
int[] digitCount = getDigitCount(n);
// check if each digit is available enough times
for (int d = 0; d < nbAllowed.length; d++) {
if (nbAllowed[d] < digitCount[d]) {
return false; // not enough d digits to represent n
}
}
return true; // enough of all digits
}
Example implementation of how to count the number of occurrences of each digit in a number n. This method returns a 10-sized array containing the number of occurrences of each digit in n. Ex: digitCount[2]
is the number of times that the digit '2' appears in the decimal representation of n
.
private static int[] getDigitCount(int n) {
int[] digitCount = new int[10]; // 10 distinct digits
Arrays.fill(digitCount, 0); // start at 0 occurrence for each digit
// special case 0
if (n == 0) {
digitCount[0] = 1; // 1 occurrence for digit '0'
return digitCount;
}
// fill digitCount with the number of occurrences of each digit in n
int digit;
while(n > 0) {
digit = n % 10; // current last digit of n
digitCount[digit]++; // increments the number of occurrences for that digit
n /= 10; // shifts the decimal number n to the right (last digit disappears)
}
return digitCount;
}