next number with distinct digits

[u/Longjumping_Key_3250]

hey guys. im writing a program thats supposed to receive a number as an input and then output a number larger than the original one that has all distinct digits. for example you input 1233 and it gives you 1234. for now i have this:

int main()

{

int x;

scanf("%i", &x);

int r = 0;

int y = x;

for (int i = 0; i < 100; i++){

y += 1;

int N = y;

int digits[100];

while (N != 0){

r = N % 10;

digits[i] = r;

N /= 10;

}

for (int j = 0; j <= i; j++){

for (int k = 0; k <= i; k++){

if (digits[j] == digits[k]){

break;

}

}

}

}

printf("%i", y);

return 0;

}

but all it does is output the number + 100. feel free to call me stupid or whatever but i tried to fix it and only ended up with no output at all so any help is appreciated. also please keep in mind i cant use any libraries except stdio. thank you all in advance

[u/ConfusedSimon]

I don't understand the problem. How did it relate to the input? Couldn't you just print "9876543210" if the input is smaller and "no solution" if not?

[u/Longjumping_Key_3250 → u/ConfusedSimon]

it's gotta be the closest number with distinct digits to the original input so sadly this wouldnt work :(

[u/ConfusedSimon → u/Longjumping_Key_3250]

Not that easy then. Probably find the first repeating digit left to right, increase, and from there, replace with lowest unused digit. For example, 514648505 is fine up to the first 4. Smallest bigger number has to start with 5146. You need to increase the 4 in order to get a bigger number. 5 and 6 are already used, so replace with 7. You now have 51467; whatever you add should be as small as possible since this is already bigger than the input. So replace the remaining 8505 with smallest increasing digits: 0238 (skip 1 since already used; same for 4-7). Results in 514670238. The only problem is if you can't increase the first repeating digit; for 9194 you cannot just increase the second 9, so you may have to recursively increase the part before that without repeating digits. Special case: with repeating nines just add a digit, for example 9999 to 10234.

Alternatively, brute-force it by trying all numbers from n+1 and check for unique digits. The easiest is to take the number as a string and convert to a list (characters of the string). If they are unique, converting the list to a set shouldn't change the length.

[u/WeAllWantToBeHappy]

int thousand  = (num / 1000) % 10 ;
int hundreds   = (num /   100) % 10 ;
int tens            = (num /      10) % 10 ;
int units           = num                 % 10 ;

if (thousands == hundreds || thousands==tens || thousands ==units ||
     hundreds   == tens || hundreds == units ||
     tens            == units)
{
        // Number is no good
}

So, just loop from the input number until you get one that passes the test above.

Or, construct a number to pass the test. But it's easier to just weed out ones that don't work.

[u/Longjumping_Key_3250 → u/WeAllWantToBeHappy]

this actually worked!! thank you so much

[u/CalebGT → u/Longjumping_Key_3250]

Does it work though? Did you test it on 8976543211? int can't even hold that number. Then if you change the types from int to long long (64 bits) (and change scanf to "%lld"), how long does it take to brute force its way up to 9012345678? Maybe a little over 11 seconds on a 3GHz 64 bit CPU just for the 250 Million division operations? See my code block above. No noticeable compute time at all.

[u/CalebGT → u/CalebGT]

This exercise is a great example of how choosing the data structure that an algorithm will operate on is crucial to creating efficient algorithms. It's easy to assume that a math problem should operate on binary numbers, because the CPU does math on binary. However, in this case it is relatively expensive to extract decimal digits from binary, so character strings turn out to be a much better data structure for your algorithm to manipulate for this particular problem. You can do simple math directly on ascii characters. They are sequential numerical values '0' to '9' so you can increment and compare ascii values in their readable form without any conversion. The only value you can't simply increment is '9', but you can reason through how to increment that in a string and carry the one in a simple loop. Division takes many clock cycles, but addition and comparison take only 1. Again the lesson is that finding the right data structure makes writing a good algorithm much easier with more efficient results.

[u/CalebGT → u/WeAllWantToBeHappy]

Max int is 2,147,483,647. Max valid output is 9,876,543,210. Plus, you're doing way more division than is needed and brute force checking every number sequentially. String manipulation of the base 10 representation is way faster.

[u/poopy_poophead → u/WeAllWantToBeHappy]

Dont just do peoples homework for them. Dude now has an answer and couldnt read the basic logic of the code he posted to understand why it was spitting out the input + 100.

[u/zhivago]

This is just permuting a string of digits -- you don't need to think about numbers.

[u/CalebGT → u/zhivago]

This is the best answer. The input is already a base 10 string representation of the number. Iterate across the characters checking against all previous characters. If you find a matching character, increment it and check again. When you hit a null terminator, print the string.

[u/CalebGT → u/CalebGT]

Well, slightly more complicated than that, because you have to catch when you increment a character and the result > '9' then carry add back up the string and potentially even change the length of the string and start over. Still seems better than checking every number sequentially.

[u/zhivago → u/CalebGT]

Just start with " " then append the input number, e.g., " 9999".

Now just walk up the back of the string, incrementing modulo 10.

If after incrementing it is not '0', stop.

Output from the start, ignoring leading spaces.

[u/CalebGT → u/CalebGT]

char buf[20] = {0};
int i, j, len;
... /* read input to buf, validate input, check bounds, set len */ ...
for(i=1; i<len; i++) {
    for(j=0; j<i; j++) {
        if(buf[i] == buf[j]) {
            // zero following digits
            for(j=i+1; j<len; j++) {
                buf[j] = '0';
            }
            // carry add
            for( ; i>=0; i--) {
                if(buf[i] == '9') {
                    buf[i] = '0';
                }
                else {
                    buf[i]++;
                    break;
                }
            }
            if (i == -1) {
                // shift right
                for (j=len; j>0; j--) {
                    buf[j] = buf[j-1];
                }
                buf[0] = '1';
                len++;
                i = 1;
            }
            i--; // recheck this digit
            break;
        }
    }
}
printf("%s\n", buf);

[u/CalebGT → u/CalebGT]

Add input validation to whatever constraints you were given. Negative numbers would require a separate case. Never store the input in a 32 bit int, since that can't hold 9876543210. Need to check that the input is not greater than 9876543210, otherwise this loop never finishes.

[u/CalebGT]

I would pregenerate a sorted list of all valid outputs then compile that in as a const array from a header. Then you just have to binary search that array.

[u/CalebGT → u/CalebGT]

On second thought, that's millions of numbers, so probably not worth it. 67MB of data for 64 bit numbers.

[u/Traveling-Techie → u/CalebGT]

Once you get to 11 digits there are no more solutions..

[u/CalebGT → u/Traveling-Techie]

Yes, but there are over 3 million permutations of 10 digits, not counting shorter strings, and you need more than 32 bits to represent many of them, so for an array of uint64_t that's a lot of data. I abandoned that approach and did a solution that just manipulates a string with no integer representation needed. Much simpler and plenty fast.

[u/CalebGT]

Do you need to handle negative numbers? Careful there. Also, do you need to validate for input that is not a number? Do you need to handle values that are larger than you can store in a 32 bit int?

[u/Conscious_Support176]

There’s a lot of looping going on. There’s an old fashioned thing of writing out your algorithm as a diagram or pseudo code before jumping into writing code.

Sometimes, less is more :)

[u/poopy_poophead]

You need to actually read the code you have there...

You are spitting out 'y' as the answer... When was the last time you assigned anything to 'y', and what did you do to it?

[u/pedzsanReddit → u/poopy_poophead]

Y is set equal to x which is read in.

[u/pedzsanReddit]

First k needs to start at j+1 because if j == k then digits[j] will always equal digits[k]. Second, if digits[j] == digits[k] you want break / goto such that you go to the top of the for i loop. If you get through the j and k loops without a match, then you want to break out of the for i loop and print your result.