Here is the simplified problem statement.
A number of candles are given each of them labelled with the digit 0-9. We have to find the minimum positive number that can not be formed with the given candles.
The input is given as an array of size 10.
Array[0] indicates the number of ‘0’ candles
Array[1] indicates the number of ‘1’ candles and so on upto Array[9].
For example:
- For input 1 6 2 1 1 2 1 1 2 0, the output is 9. Since we have zero ‘9’ candles, the minimum number that can not be formed is 9.
- For input 2 3 2 2 1 2 1 1 1 1, the output is 44; because we have only one ‘4’ candle.
- For input 0 1 1 1 1 1 1 1 1 1, the output is 10; We have one ‘1’ candle so we can not form 10 with the given candles.
Note: Even though we don’t have any ‘0’ candles, the minimum number is not 0 because the answer should be a positive number.
Here is the approach to solve this problem.
- Identify the left most digit with minimum count. It can be ‘0’ also.
- Form a number by repeating the minimum digit (count+1) times
- A special case occurs when ‘0’ candle has minimum count, we have to prefix ‘1’ to it, as we can not have all zeros.
- One more special case is when 0 and some other digit has the same minimum count, we have to consider the left most non-zero digit. Take a look at the following case to understand the situation.
- 2 3 4 7 6 2 8 3 5 9
- Both ‘0’ and ‘5’ has the count of 2. If we consider zero, the output becomes 1000 according to the above algorithm. If we consider ‘5’, the output becomes 555. Since 555 < 1000; the answer should be 555.
Here is the C++ code for this problem.