具有不同相邻数字的最小更大数

Question

我们给定一个数n 1<=n<= 10^18，我们要找到大于n且相邻数字不同的最小数，例如对于 1000，答案是 1010，对于 99，答案是 101。如果 n<=10^9，方法很简单。但是计算更高的值需要很多时间。如何实现它以便它也可以快速计算 10^18？。我的方法如下，它仅适用于 n<=10^9.

#include <iostream>
using namespace std;


bool valid(int x){
    if(x==0)return 1;
    if(x%10==(x/10)%10)return 0;
    return valid(x/10);
}


unsigned long long n;
int main() {
    cin>>n;
    n++;
    while(1){
        if(valid(n)){
            cout<<n;
            return 0;
        }
        n++;
    }
}

例如 1000 的答案是 1010，99 的答案是 101。

Answer 1

我的解决方案是基于相邻的数字，当我们遇到“99”时有额外的逻辑。我不太喜欢它，但也许它会解决您的问题或有助于编写更好的解决方案。

public static int Test(string nStr)
{
    var n = int.Parse(nStr);
    var needRestartCheck = true;
    while (needRestartCheck)
    {
        needRestartCheck = false;
        for (var i = 0; i < nStr.Length - 1; i++)
        {
            var first = nStr[i];
            var second = nStr[i + 1];
            if (first == second)
            {
                n += (int)Math.Pow(10, nStr.Length - 2 - i);
                nStr = n.ToString();
                needRestartCheck |= first == '9';
            }
        }
    }
    return n;
}

Answer 2

My approach is following, it works only for n<=10^9

这可能是由于这种明显的类型不匹配：

bool valid(int x) {
unsigned long long n;
if (valid(n)) {

当您将 n 传递给 valid() 时，您丢弃了一半的位，因为它仅在 int 上运行，而不是 unsigned long long。这是您的逻辑的重新实现，它修复了该问题，但每次迭代仅进行 two 划分，而不是 four:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool valid(unsigned long long x) {
    unsigned long long remainder = x % 10;

    while (x) {

        unsigned long long quotient = x / 10;
        unsigned long long adjacent = quotient % 10;

        if (remainder == adjacent) {
            return false;
        }

        x = quotient;
        remainder = adjacent;
    }

    return true;
}

int main(int argc, char *argv[]) {
    char *pointer;
    unsigned long long n = strtoull(argv[1], &pointer, 10) + 1;

    while (true) {
        if (valid(n)) {
            printf("%llu\n", n);
            break;
        }

        n++;
    }

    return 0;
}

示例

> dc
10 10 ^ p
10000000000
> ./a.out 10000000000
10101010101
> dc
10 11 ^ p
100000000000
> ./a.out 100000000000
101010101010
>

但不幸的是，攻击 10^18

还是太慢了

Thanks, but this post was about slowness – Sandro Jologua

让我们使用对数和 10 的幂以一种完全不同且快速的方式来解决这个问题。不转换为字符串，而是使用数学来解决问题：

#include <stdio.h>
#include <stdlib.h>

unsigned logTen(unsigned long long number) {
    unsigned power = 0;

    while (number >= 10) {
        power += 1;
        number /= 10;
    }

    return power;
}

unsigned long long expTen(unsigned n) {
    unsigned long long product = 1;

    while (n > 0) {
        product *= 10;
        n -= 1;
    }

    return(product);
}

unsigned long long next_no_adjacent(unsigned long long number) {
    number += 1;

    unsigned power = logTen(number);

    while (power > 0) {

        unsigned long long multiplier = expTen(power);
        unsigned long long digit = (number / multiplier) % 10;

        unsigned long long adjacent_multiplier = expTen(power - 1);
        unsigned long long adjacent_digit = (number / adjacent_multiplier) % 10;

        while (digit == adjacent_digit) {

            number = ((number + adjacent_multiplier) / adjacent_multiplier) * adjacent_multiplier;

            digit = (number / multiplier) % 10;
            adjacent_digit = (number / adjacent_multiplier) % 10;
        }

        --power;
    }

    return number;
}

int main(int argc, char *argv[]) {
    char *pointer;
    unsigned long long n = strtoull(argv[1], &pointer, 10);

    printf("%llu\n", next_no_adjacent(n));

    return 0;
}

示例

> dc
10 19 ^ p 
10000000000000000000
> time ./a.out 10000000000000000000
10101010101010101010
0.001u 0.001s 0:00.00 0.0%  0+0k 0+0io 0pf+0w
>

我们必须定义我们自己的以 10 为底的幂和对数函数，因为 C 库中提供的函数在 double 上运行，但我们需要使用 unsigned long long.

Answer 3

我自己解决了

#include <bits/stdc++.h>
#define ll unsigned long long

using namespace std;

bool noDec(string str,int i,ll num){
    str[i+1]--;
    return stoll(str)>num;
}

ll num;
string str;
int main() {
    cin>>num;
    str=to_string(num+1);
    for(int i=0; i<str.length()-1; i++){
        if(str[i]==str[i+1]){
            if(str[i]!='9'){
                if(noDec(str,i,num)&&str[i]!='0')str[i+1]--;
                else str[i+1]++;
            }
            else{
                if(i==0){
                    str='1'+string(str.length(),'0');
                }else{
                    str[i-1]++;
                    for(int j=i; j<str.length(); j++){
                        str[j]='0';
                    }
                }
            }i=0;
        }
    }
    if(str[0]==str[1]&&str[0]=='9'){
        str=string((ll)log10(num)+2,'1');
        for(int i=1; i<str.length(); i+=2)
            str[i]='0';
    }
    cout<<str;
}

具有不同相邻数字的最小更大数

minimum greater number with different adjacent digits

algorithm

number-theory

data-structures