Given an integer N. What is the smallest integer greater than N that only has 0 or 1 as its digits?

Question

I have an integer N. I have to find the smallest integer greater than N that doesn't contain any digit other than 0 or 1. For example: If N = 12 then the answer is 100. I have coded a brute force approach in C++.

int main() {
    long long n;
    cin >> n;

    for (long long i = n + 1; ; i++) {
        long long temp = i;
        bool ok = true;
        while (temp != 0) {
            if ( (temp % 10) != 0 && (temp % 10) != 1) {
                ok = false;
                break;
            }
            temp /= 10;
        }
        if (ok == true) {
            cout << i << endl;
            break;
        }
    }
}

The problem is, my approach is too slow. I believe there is a very efficient approach to solve this. How can I solve this problem efficiently?

Answer 1

1. Increment N,

2. Starting from the left, scan until you find a digit above 1. Increment the partial number before it and zero out the rest.

E.g.

12 -> 13 -> 1|3 -> 10|0
101 -> 102 -> 10|2 -> 11|0
109 -> 110 -> 111|
111 -> 112 -> 11|2 -> 100|0
198 -> 199 -> 1|99 -> 10|00
1098 -> 1099 -> 10|99 -> 11|00
10203 -> 10204 -> 10|204 -> 11|000
111234 -> 111235 -> 111|235 -> 1000|000
...

---

Proof:

The requested number must be at least N+1, this is why we increment. We are now looking for a number greater or equal.

Let us call the prefix the initial 0/1 digits and suffix what comes after. We must replace the first digit of the suffix by a zero and set a larger prefix. The smallest prefix that fits is the current prefix plus one. And the smallest suffix that fits is all zeroes.

---

Update:

I forgot to specify that the prefix must be incremented as a binary number, otherwise forbidden digits could appear.

Answer 2

Another possibility would be the following one:

• You start with the largest decimal number of the type "1111111...1111" supported by the data type used

  The algorithm assumes that the input is smaller than this number; otherwise you'll have to use another data type.

  Example: When using long long, you start with the number 1111111111111111111.

• Then process each decimal digit from the left to the right:
  • Try to change the digit from 1 to 0.
  • If the result is still larger than your input, do the change (change the digit to 0).
  • Otherwise the digit remains 1.

Example

Input = 10103
Start:  111111
Step 1: [1]11111, try [0]11111; 011111 > 10103 => 011111 
Step 2: 0[1]1111, try 0[0]1111; 001111 < 10103 => 011111
Step 3: 01[1]111, try 01[0]111; 010111 > 10103 => 010111
Step 4: 010[1]11, try 010[0]11; 010011 < 10103 => 010111
Step 5: 0101[1]1, try 0101[0]1; 010101 < 10103 => 010111
Step 6: 01011[1], try 01011[0]; 010110 > 10103 => 010110
Result: 010110

Proof of correctness:

We process digit by digit in this algorithm. In each step, there are digits whose value is already known and digits whose values are not known, yet.

In each step, we probe the leftmost unknown digit.

We set that digit to "0" and all other unknown digits to "1". Because the digit to be probed is the most significant of the unknown digits, the resulting number is the largest possible number with that digit being a "0". If this number is less or equal the input, the digit being probed must be a "1".

On the other hand, the resulting number is smaller than all possible numbers where the digit being probed is a "1". If the resulting number is larger than the input, the digit must be "0".

This means that we can calculate one digit in each step.

C code

(The C code should work under C++, too):

long long input;
long long result;
long long digit;

... read in input ...

result = 1111111111111111111ll;
digit = 1000000000000000000ll;

while( digit > 0 )
{
    if(result - digit > input)
    {
        result -= digit;
    }
    digit /= 10;
}

... print out output ...