minimum greater number with different adjacent digits

Question

We are a given number n 1<=n<= 10^18, and we have to find minimal number that's greater than n and also it's adjacent digits are different, for example for 1000, answer is 1010, for 99, answer is 101. The approach is simple if n<=10^9. But it takes a lot of time to calculate for higher values. How it can be implemented so that it calculates quickly for 10^18 also?. My approach is following, it works only for 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++;
    }
}

for example for 1000, answer is 1010, for 99, answer is 101.

Answer 1

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

This is probably due to this glaring type mismatch:

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

You're throwing away half the bits of n when you pass it to valid() as it only operates on int, not unsigned long long. Here's a reimplementation of your logic which fixes that issue but only does two divisions on each iteration instead of 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;
}

EXAMPLE

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

But unfortunately it's still way too slow to attack 10^18

Thanks, but this post was about slowness – Sandro Jologua

Let's approach this a completely different, and fast, way using logarithms and powers of 10. Not converting to a string but using math to solve the problem:

#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;
}

EXAMPLE

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

We have to define our own base 10 power and logarithm functions as the ones provided in the C library operate on double but we need to work with unsigned long long.

Answer 2

Solved it on my own

#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;
}

Answer 3

My solution is based on adjacent digits, with additional logic when we met "99". I don't like it really much, but maybe it will solve your problem or help to write better solution.

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;
}