C: Finding closest number to the first without repeating digits from the second number?

Question

I read two numbers, both int.

What I need to do is do print the number higher than but closest to the first number, such as 378, but which doesn't contain any of the digits from the second number, for example, 78.

Input: 378 78, output: 390 because that's the lowest number above 378 that doesn't contain any of the digits of 78.

Input: 3454 54, output: 3600 because 3600 is the first closest that doesn't contain 5 or 4, the digits of 54.

I am trying to do this by getting the latest modulus digits of the first number, from the length of the second. For example:

378 78

378 mod 100 == 78, then compare 78 and 78 digits, and if there is same digit move on to 379, then check for 379 mod 100 == 79. When comparing 79 and 78, 7 is the same digit.

And so on until we get 390 for example. This should work for all N-size numbers.

Here is what I've done so far...and that's almost nothing.

#include <stdio.h>

int main()
{
    int number1, number2;
    int closest = number1 + 1;
    scanf("%d %d",&number1,&number2);
    
    int count_modulus = 1;
    
    while(number2)
    {
        count_modulus = count_modulus * 10;
        number2 = number2 / 10;
    }
    int mod = count_modulus;
    int n2 = number2;
    while(number1)
    {
        int remain = number1 % mod;
        while(remain)
        {
            if((remain % 10 == number2 % 10))
            {
                
            }
            else
            {
                
            }
        }
    }
    printf("%d",closest);
    return 0;
}

`int closest = number1 + 1;` here `number1` in uninitialized. — Sourav Ghosh, Oct 28 '14 at 11:40
It is ok because if i have 378 and 78 it needs to start from 379. — Skokaj Skokaj, Oct 28 '14 at 11:50
check your code. you are doing `+1` before **having** the value. — Sourav Ghosh, Oct 28 '14 at 11:53
it is okay, i only need the code in tha brackets in the second while, closest is increase by one because i need to check the next number, and to manipulate with it in the while. — Skokaj Skokaj, Oct 28 '14 at 12:01
It appears your approach only considers number greater than `number1`. Why not consider numbers less than `number1` if you want to find "closest"? 370 70 --> 369 — chux - Reinstate Monica, Oct 28 '14 at 15:41
I need to find the largest closest to the number in my case 378, i have to find closest less than 378 too, but in different task. Any help? — Skokaj Skokaj, Oct 28 '14 at 17:46

score 0 · Answer 1 · edited May 23 '17 at 11:56

I'm not entirely convinced that your modulo method is going to work since, if you start with 7823 and 78, then 7823 mod 100 gives you 23 which has no digits in common with 78 even though 7823 does.

But, even if I've misunderstood the specification and it did work, I think there's a better way. First things first, how to score a number based on what digits it contains.

Provided your integers have at least ten bits (and they will, since the standard mandates a range that requires sixteen), you can just use a bit mask with each bit representing whether the number holds a digit. We can use a normal int for this since ten bits will get us nowhere near the sign bit that may cause us issues.

The code for scoring a number is:

// Return a bitmask with the bottom ten bits populated,
//   based on whether the input number has a given digit.
// So, 64096 as input will give you the binary value
//     000000 0000111010
//   <-unused ^  ^ ^   ^
//            9876543210 (digits)

int getMask (int val) {
    int mask = 0;                        // All start at 0
    while (val > 0) {                    // While more digits
        mask = mask | (1 << (val % 10)); // Set bit of digit
        val = val / 10;                  // Move to next digit
    }
    return mask;
}

The "tricky" bit there is the statement:

mask = mask | (1 << (val % 10));

What it does it get the last digit of the number, with val % 10 giving you the remainder when dividing val by ten. So 123 % 10 gives 3, 314159 % 10 gives 9 and so on.

The next step is to shift the binary 1 that many bits to the left, with 1 << (val % 10). Shifting a 1-bit four places left would give you the binary value 10000 so this is simply a way to get the 1-bit in the correct position.

Finally, you bitwise-OR the mask with that calculated value, effectively setting the equivalent bit in the mask, keeping in mind that the bits a | b gives you 1 if either or both a and b are 1.

Or you can check out one of my other answers here for more detail.

So, I hear you ask, how does that bitmask help us to find numbers with no common digits. Well, that where the AND bitwise operator & comes in - this only gives you a 1 bit if both input bits are 1 (again, see the link provided earlier for more detail on the bitwise operators).

Once you have the bitmask for your two numbers, you can use & with them as per the following example, where there are no common digits:

Number  Bitmask
               9876543210
------  ----------------
314159  000000 1000111010
   720  000000 0010000101
        ----------------- AND(&)
        000000 0000000000

You can see that, unless the bit position has a 1 for both numbers, the resultant bit will be 0. If any numbers are in common at all, it will be some non-zero value:

Number  Bitmask      v
               9876543210
------  -----------------
314159  000000 1000111010
   320  000000 0000001101
        ----------------- AND(&)
        000000 0000001000
                     ^
                     The bit representing the common digit 3.

And that leads us to the actual checking code, something relative easy to build on top of the scoring function:

#include <stdio.h>

int main (int argc, char *argv[]) {
    // Default input numbers to both zero, then try
    //   to get them from arguments.

    int check = 0, exclude = 0, excludeMask;
    if (argc > 1)
        check = atoi(argv[1]);
    if (argc > 2)
        exclude = atoi(argv[2]);

    // Get the mask for the exclusion number, only done once.

    excludeMask = getMask (exclude);

    // Then we loop, looking for a mask that has no
    //   common bits.

    printf ("%d -> ", check);
    //check++;
    while ((excludeMask & getMask (check)) != 0)
        check++;
    printf ("%d\n", check);

    return 0;
}

The flow is basically to get the numbers from the arguments, work out the bitmask for the exclusion number (the one that has the digits you don't want in the result), then start looking from the check number, until you find one.

I've commented out the initial check++ since I'm not sure whether you really wanted a higher number than the one given, or whether 123 with an exclusion of 98 should give you the actual starting number of 123. If not, just uncomment the line.

And there you have it, as shown in the following transcript, which includes your test data amongst other things:

$ ./myprog 378 78
378 -> 390

$ ./myprog 3454 54
3454 -> 3600

$ ./myprog 123 98  # would give 124 if 'count++' uncommented
123 -> 123

$ ./myprog 314159 6413
314159 -> 500000

It does have one potentially fatal flaw but one that's easy enough to fix if you check the exclusion bitmask before you start looking for. I'll leave that as an exercise for the reader, but just think about what might happen with the following command:

$ ./myprog 1 154862397

And, of course, if you want to go the other way (lower numbers), it's a matter of decrementing check rather then incrementing it. You may also need to get a bit smarter about what you want to happen if you go negative, such as with:

$ ./myprog 1 102

The code as it currently stands may not handle that so well.

C: Finding closest number to the first without repeating digits from the second number?

1 Answers1