How to know the lowest value that is not in a group of numbers

Question

I have a group of numbers 0 to 9 => {0 .. 9}, but another group that represent each amount of {0 .. 9} we have, for example:

0 => 1
1 => 2
2 => 3
3 => 4
4 => 5
5 => 6
6 => 7
7 => 8
8 => 9
9 => 1

The lowest value that we cannot represent with those groups is 99. They are digits to represent a number, for example if we only have:

2 => 2
7 => 1

The lowest value should be 0 or 1, and the possibilities are, 2, 7, 22, 27, 72, 227, 272, 722.

I am doing an algorithym in java to calculate the lowest value that we cannot represent, but I even do not very well how to do it, and I need a little or big help.

Thanks.

Answer 1

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;
}

Answer 2

The problem can be solved by not applying brute-force. There are four cases to distinguish in the given order, which means if we evaluate case 3, case 1 and 2 did not apply:

1. There is at least one digit with an amount of zero: then the smallest of those digits is not representable.

2. The set of digits with the smallest available amount does not contain the digit zero: now we know the amount is greater than zero and hence repeating the smallest of those digits one more time than available digits is the smallest non representable number.

3. The set of digits with the smallest available amount has a size of one: now we know it has to be the digit zero having an amount greater than zero. And we know the next greater digit, the one is available, due to passed through case 1. Hence the number composed of a leading 1 followed by amount many zeros is the smallest non representable number.

4. We know the set of digits with the smallest available amount contains the digit zero and at least one more digit: hence repeating the second smallest digit of this set one more time than available digits is the smallest non representable number.

Expressed in terms of a Java program the main algorithm looks like this:

private static final List<Integer> DIGIT_POOL =
    Arrays.asList(2, 1, 3, 4, 5, 6, 7, 8, 9, 1);

public static void main(String[] args) {
    Map<Integer, List<Integer>> amountToDigits = mapToDigits(DIGIT_POOL);
    String number;
    int amount = amountToDigits.keySet().iterator().next();
    List<Integer> digits = amountToDigits.get(amount);
    if (amount == 0) {
        number = number(digits.get(0), 1);
    } else if (!digits.contains(0)) {
        number = number(digits.get(0), amount + 1);
    } else if (digits.size() == 1) {
        number = paddedWithZero(1, amount + 2);
    } else {
        number = number(digits.get(1), amount + 1);
    }
    System.out.println(number);
}

private static SortedMap<Integer, List<Integer>> mapToDigits(List<Integer> digitAmounts) {
    SortedMap<Integer, List<Integer>> amountToDigits = new TreeMap<>();
    for (int digit = 0; digit <= 9; digit++) {
        int amount = digitAmounts.get(digit);
        List<Integer> digits = amountToDigits.get(amount);
        if (digits == null) {
            digits = new ArrayList<>();
            amountToDigits.put(amount, digits);
        }
        digits.add(digit);
    }
    return amountToDigits;
}

Constructing the resulting non representable number requires the following helper methods:

private static String paddedWithZero(Integer digit, int length) {
    char[] letters = letters(0, length);
    letters[0] = digit.toString().charAt(0);
    return new String(letters);
}

private static String number(Integer digit, int length) {
    return new String(letters(digit, length));
}

private static char[] letters(Integer digit, int length) {
    char[] letters = new char[length];
    Arrays.fill(letters, digit.toString().charAt(0));
    return letters;
}

The total complexity of the algorithms is the sum of:

• mapping n digits to their amounts: O(n)

• distinguishing between four cases: O(1)

• constructing a number of lenght m + 1, where m is the smallest amount of available digits: O(m)

Hence the total complexity is O(max(n, m)) which is linear. This solution works pretty fast for very large amounts (1k and greater) of given digits.

Answer 3

When you're going from the lowest point, it's usually prudent to start at 0. So we'll need some sort of loop, and because we don't know how many times we'll look, we'll implement a while loop.

boolean numberFound = false;

while(!numberFound) {
    // Loops while a number has not been found.
}

We also need to keep track of our current number, so we'll declare a pointer p.

int p = 0;

boolean numberFound = false;

while(!numberFound) {
}

Now, let's assume you've got all these values in an array. So 1 is in position 0, 2 is in position 1 etc. You need to get the first value of p. Now, for any value of p between 9 and 0 inclusively, we can just grab the number of occurrences, so we do something like:

if(p <= 9 && p >= 0) {
     // Get the number of occurrences.
     int numberOfDigits = digits[p] // Digits is your array as described above.

     if(numberOfDigits == 0) {
         // You only need one digit to represent this number.
         // If you don't have one digit, you've just found a number that works.
         numberFound = true;
     }
}

Next, you'll need to deal with numbers larger than 9. Because this has more than one digit, you'll need to do this in stages:

• First, convert the Integer into a String.
• Next, cycle through each character in that String.
• Parse that character back to an integer, and grab the value from the array.
• Get the number of times that character occurs in a string.
• If the value in the array is less than the number of times that value occurs..
  • You've found a number.
• Else, keep looping.

Good luck with the last part of the solution. As a general rule, when it looks like someone hasn't made much of an effort with a problem, I don't provide the entire solution.

Answer 4

My understanding is the same as Joffrey's algo.

Write a method like:

public boolean checkIfInGroup(int value) {
    ...
}

then you can create a loop in your outer method:

int n=0;
while (checkIfInGroup(n)) {
    n++;
}
return n;

The challenge would be how to optimize the checkIfInGroup() method.

Answer 5

If I understood you correctly, you have one Array with numbers from 0 - 9 and another one with the same numbers in a different order. You want to know, which number is the one below the smallest displayable. So, if I understood you correctly, it should always be -1, because, if you have numbers from 0 - 9, 0 is the lowest displayable number, so -1 is the one beneath that. Could I help?