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

标签： algorithmdata-structuresnumber-theory

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.