给定一个整数N。大于N且仅以0或1为数字的最小整数是什么？

Question

我有一个整数N。我必须找到大于N的最小整数，该整数不包含0或1之外的任何数字。例如：如果N = 12答案为100。我已经用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;
        }
    }
}

问题是，我的方法太慢了。我相信有一个非常有效的方法可以解决这个问题。如何有效解决此问题？

Answer 1

1. 增量N

2. 从左侧开始，进行扫描，直到找到高于1的数字为止。递增部分编号，然后将其其余部分归零。

例如

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
...

证明：

请求的数字必须至少为N + 1，这就是我们递增的原因。我们现在正在寻找更大或相等的数字。

让我们将前缀称为开头的0/1数字，并在其后添加后缀。我们必须将后缀的第一位替换为零，并设置较大的前缀。合适的最小前缀是当前前缀加1。合适的最小后缀是全零。

更新：

我忘记指定前缀必须作为二进制数递增，否则可能会出现禁止的数字。

Answer 2

另一种可能性是以下一种：

• 您从所使用的数据类型支持的“ 1111111 ... 1111”类型的最大十进制数开始

  该算法假定输入小于此数字。否则，您将不得不使用其他数据类型。

  示例：使用时long long，请从数字开始1111111111111111111。

• 然后从左到右处理每个十进制数字：
  • 尝试将数字从1更改为0。
  • 如果结果仍然大于您的输入，请进行更改（将数字更改为0）。
  • 否则，数字仍为1。

例

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

正确性证明：

我们在此算法中逐位处理。在每个步骤中，都有其值已知的数字和尚不知道其值的数字。

在每一步中，我们都会探查最左边的未知数字。

我们将该数字设置为“ 0”，并将所有其他未知数字设置为“ 1”。因为要探测的数字是未知数字中的最高位，所以结果数字是最大可能数字，该数字为“ 0”。如果此数字小于或等于输入，则所探测的数字必须为“ 1”。

另一方面，所得到的数字小于要探查的数字为“ 1”的所有可能的数字。如果结果数字大于输入的数字，则该数字必须为“ 0”。

这意味着我们可以在每个步骤中计算一位数。

C代码

（C代码也应在C ++下工作）：

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 ...