recursive checking between 2 numbers

Question

I got a task for hw to make a recursive function that checks between 2 unsigned long long numbers and check for common digits if there is its will print the common digits (its starts checking from right to left- when a match found we stop and print that digit) if there is no same digits its will return -1

The problem is I could make it work for the first and last example but I am having trouble dealing with the second example.
any hints will be appreciated :)

```c
int findCommonDigit(unsigned long long n1, unsigned long long n2) {

    int temp1 = 0, temp2 = 0;
    if (n1 == 0 || n2 == 0)
        return -1;
    temp1 = n1 % 10;
    temp2 = n2 % 10;
    if (temp1 == temp2)
        return temp1;
    return findCommonDigit(n1 / 10, n2 / 10);

}

Answer 1

This is what I came up with based on your and my test cases.

Twice the recursion twice the fun!

#include <stdio.h>

#define DEBUG_FUNCTION 0

int compareN1Digits(unsigned long long n1, unsigned long long n2)
{
    int n1RightDigit = n1 % 10;
    if(DEBUG_FUNCTION) printf("    n1 right most digit : %d\n", n1RightDigit);
    
    int result = -1;
    if (n1RightDigit != n2)
    {
        if(DEBUG_FUNCTION) printf("Not a match.\n");
        if (n1 > 10)
        {
            result = compareN1Digits(n1 / 10, n2);
        }
    }
    else
    {
        result = n1RightDigit;
    }
    
    return result;
}

int findCommonDigit(unsigned long long n1, unsigned long long n2)
{
    int n2RightDigit = n2 % 10;
    if(DEBUG_FUNCTION) printf("n2 right most digit : %d\n", n2RightDigit);
    
    int result = -1;

    result = compareN1Digits(n1, n2 % 10);

    if (result == -1)
    {
        if (n2 >= 10)
        {
            result = findCommonDigit(n1, n2 / 10);
        }
    }
    
    return result;
}

void RunTestCase(unsigned long long n1, unsigned long long n2, int expectedResult)
{
    int result;
    
    result = findCommonDigit(n1, n2);
    if (result == expectedResult)
    {
        printf("Corrent Result\n\n");
    }
    else
    {
        printf("Result NOT corrent!\n\n");
    }
}
    
int main()
{
    // Test Case 1
    // 22222446, 113355578889 => function will give back -1
    RunTestCase(22222446, 113355578889, -1);

    // Test Case 2
    // 13259438, 2 => function will give back 2
    RunTestCase(13259438, 2, 2);

    // Test Case 3
    // 112233445, 112233445 => function will give back 5.
    RunTestCase(112233445, 112233445, 5);
    
    // Test Case 4
    // 2, 13259438 => function will give back 2
    RunTestCase(2, 13259438, 2);

    // Test Case 5
    // 12034, 567809 => function will give back 0
    RunTestCase(12034, 567809, 0);
    
    // Test Case 6
    // 1, 1 => function will give back 1
    RunTestCase(1, 1, 1);
    
    // Test Case 7
    // 0, 0 => function will give back 0
    RunTestCase(0, 0, 0);

    return 0;
}

Answer 2

So, the task, as I understand it, is to determine whether or not two numbers share at least one digit. Constraints are:

• Scan right to left.
• In the case of (21, 12) return 1, not 2. (As per your commentary.)
• The solution should be a recursive function.

Right-O. So, the trick is to compare every digit in the first number with every digit in the second number. There are quite a few ways to optimize this, but we will stick with an O(n²) brute-force method.

Given 123 and 456:

• compare 3 with 6
• compare 3 with 5
• compare 3 with 4
• compare 2 with 6
• compare 2 with 5
• compare 2 with 4
• compare 1 with 6
• compare 1 with 5
• compare 1 with 4

Hopefully you can see that that was a nested loop:

for each digit in N1:
  for each digit in N2:
    match?

Conveniently, getting the rightmost (“least-significant”) digit value is a simple remainder operation:

int digit = number % 10;

After that we modify the number to shift all the digit places down one using integer division:

number = number / 10;

We want to use recursion (instead of a looping construct like while or for), so we need to transform each one of those loops into a recursive function call.

Basic Recursion

A recursive function works by having one or more termination conditions. Failing the termination condition, it just calls itself with updated arguments.

For simple example, we can take a counting loop:

void print_START_to_STOP( int start, int stop )
{
  for (;  start < stop;  start = start+1)
    printf( "%d\n", start );
}

And make it recursive:

void print_START_to_STOP( int start, int stop )
{
  if (!(start < stop)) return;           // termination condition
  printf( "%d\n", start );               // (loop body)
  print_START_to_STOP( start+1, stop );  // invoke next iteration
}

Take a few minutes to convince yourself that those two functions are equivalent. One uses an explicit loop. One uses recursion.

Inner Loop

Let’s start easy and work on a recursive function for the inner loop:

bool isDigitInNumber( int digit, unsigned long long number )
{
  ...
}

As recursion needs at least one termination condition, the first thing to check is if there are any digits left in number to check against the argument digit. If not, there is no match.

  if (number == 0) return false;

The next thing to do is check to see if the least-significant digit of number matches the digit. If it does, we have another termination condition:

  if ((number % 10) == digit) return true;

Otherwise we are left needing to check the remaining digits in number. This is where we invoke recursion:

  return isDigitInNumber( digit, number/10 );

Zero?

You might ask, “What if digit is 0 and number has a 0 in it?”
Give it a try. Does it work for number == 201?

“Okay, so what if digit is 0 and number is also 0?”
That is a good question. Should findCommonDigit( 0, 0 ) return 0 or -1?

(Chances are your professor expects findCommonDigit( 0, 0 ) to return -1. I personally think it would be more correct if it returned 0. The only thing that shouldn’t return 0 is if either one of the numbers does not have an embedded zero, such as 123 and 456, and 0 and 123.)

Let’s come back to this in a minute.

Reflection

Let’s think about what we’ve done to simplify our problem:

• isDigitInNumber( 3, 456 )
• isDigitInNumber( 2, 456 )
• isDigitInNumber( 1, 456 )

If any one of those is true, then we can return the matching digit. Otherwise we return -1.

You should also notice that there is still an outer loop to conquer.

Outer Loop

For the outer loop, we can create a new recursive function that makes use of the last recursive function.

Take a second and think about what this recursion is looping over: N1. Just as the last function loops over N2 and gets the digit-to-compare by using remainder on N2, this recursive function loops over N1 and gets the digit-to-compare by using remainder on N1:

int digit_to_compare = n1 % 10;

Again we need some termination conditions and a recursion.

When do we stop and return -1?
(After looping through all digits of N1 and not finding a match using isDigitInNumber().)
So... when N1 is zero we are done. No match. Return -1.

  if (n1 == 0) return -1;

Otherwise we need to try to match the digit-to-compare with all the digits in N2:

  if (isDigitInNumber( digit_to_compare, n2 )) return digit_to_compare;

And finally, the digit wasn’t matched, we need to recurse on the next digit in N1:

  return findCommonDigit( ... );

You are basically done.

Zero Redux

Now back to that tricky question about zeros.

Remember that the inner-loop algorithm could not check for the possibility of zero matching zero. But that’s okay. It wasn’t the right place to check.

The right place is before you do any loops at all. Right at the beginning of your algorithm, check to see if N1 == N2. If it does, then the rightmost digit of both numbers is the same. Even if both numbers are zero.

int findCommonDigit( ... )
{
  if (n1 == n2) return (n1 % 10);  // return the matching digit, which might be 0
  return findCommonDigit_Impl( n1, n2 );
}

You will have had to rename the last findCommonDigit() function to findCommonDigit_Impl(), of course.

So many functions! What the double-hockeysticks?!

In order to handle the special condition of zeros we had to add yet another function to the mix.

That is kind of unavoidable. Otherwise we can’t tell the difference between findCommonDigit( 123, 0 ) and findCommonDigit( 0, 0 ), and the result differs between ( 123, 0 ) and ( 0, 123 ).

Anyway, we now have have three functions:

bool isDigitInNumber( int digit, unsigned long long number );
int findCommonDigit_Impl( unsigned long long n1, unsigned long long n2 );
int findCommonDigit( unsigned long long n1, unsigned long long n2 );

The last one is the one that gets invoked by the user:

int main(void)
{
  printf( "%d\n", findCommonDigit( 1234, 2 ) );

The other two are the recursive functions, and do not get invoked by the user.

It is entirely possible to combine these all into a single recursive function.

Don’t waste your time though. Doing that increases complexity, and you would have to add additional formal arguments to deal with it. (Or use global variables or some other Don’t-Do-That-Crufty hack.)

It is entirely okay to have useful helper functions. And when dealing with recursion, this kind of multiple-function structure is actually very common and normal.

Hopefully this wasn’t too long-winded, nor gave away the answer too easily. Much of the time spent here was to help think your way through designing a recursive algorithm, so that when you have to do it again in the future you won’t be utterly lost. (Recursion is hard!)

AAAANNNND, hopefully your classmates will get it too, but without producing an exact copy of you code, lol. Professors want you to learn, not cheat off the internet, and I’ve made this fairly easy to draw that kind of conclusion, alas.

P.S

BTW, you might get away with using a loop inside your recursive function: an explicit inner loop for the digits of N2 and recursion for the outer loop over N1. IDK if that is acceptable. This answer assumes no loops allowed.

Answer 3

You can write a while loop until "n2 > 0" in main function. For every digit you will call "findCommonDigit" function and check is the return value is -1 or not. If you get a digit that is not -1 then print it and break the While loop. After the while loop you can write printf("-1"). For that you have to change this return findCommonDigit(n1 / 10, n2 / 10); to this return findCommonDigit(n1 / 10, n2);

Otherwise you can change your function to this,

int findCommonDigit(unsigned long long n1, unsigned long long n2) {
    int temp1 = 0, temp2 = 0;
    if (n1 == 0 || n2 == 0){
        return -1;
    }
    temp1 = n1 % 10;
    temp2 = n2 % 10;
    if (temp1 == temp2){
        return temp1;
    }
    n1 /= 10;
    return findCommonDigit(n1, n2);
    n2 /= 10;
    return findCommonDigit(n1, n2);
}

Answer 4

You can use a loop based function instead like following:

int findCommonDigit(unsigned long long n1, unsigned long long n2) {
    int digitN1[11] = {0}, digitN2[11] = {0};
    while(n1) {
        int x = n1 % 10;
        n1 /= 10;
        digitN1[x] = 1;
    }
    while(n2) {
        int x = n2 % 10;
        n2 /= 10;
        digitN2[x] = 1;
    }
    for(int i=0; i<10; i++) {
        if(digitN1[i] && digitN2[i]) {
            return i;
        }
    }
    return -1;
}

Here digitN1 and digitN2 are two flag arrays used to store whether digits[0..9] are set on numbers n1 and n2 respectively. Then we use a for loop to check whether any digit is on both numbers or not. If no common digits found, -1 is returned.