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?
Increment N,
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 -> 110|
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments