Write a function that computes how many digits two positive integers m and n have in common

I am very new at c++, and like I mentioned in the title, I have no ideas how to even start the problem, hope someone can help me. thanks a lot.

Write a function that computes how many digits two positive
integers m and n have in common. For example, if m is 112358 and
n is 179881, then the result is 2 because the numbers have the digits
1 and 8 in common. It does not matter how often a digit occurs.
One possible way to do it:

convert each number into a C++ string, remove any repeating digits, and then compute which digits are the same in both now-stringized numbers.

Write some code first and if you are having problems people can point out ways to make it work.
Last edited on
Check if a number contains a particular digit:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// return true if the number contains digit d
bool has_digit( unsigned int number, unsigned int d )
{
    if( number < 10 ) return number == d ; // single digit number

    while( number > 9 ) // till there is only one digit left
    {
        // number%10 yields the last (rightmost) digit of numbe
        if( number%10 == d ) return true ; // found the digit

        number /= 10 ; // number/=10 chops off the rightmost digit of the number
    }

    return false ;
}

With this, you should now be able to examine the digits of a number one by one.
Use of valarray to produce a quasi-histogram. (Changing line 8 to for ( ; n; n /= 10 ) f[n%10]++; would produce an actual histogram, but preclude the use of valarray operations to do the counting via the sum on line 17.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <valarray>
using namespace std;

valarray<int> isPresent( int n )
{
   valarray<int> f( 0, 10 );
   for ( ; n; n /= 10 ) f[n%10] = 1;
   return f;
}

int main()
{
   int A, B;
   cout << "Input A and B: ";
   cin >> A >> B;
   cout << "Number of digits in common = " << ( isPresent( A ) * isPresent( B ) ).sum();
}
Input A and B: 112358 179881
Number of digits in common = 2



Stringify and look for common characters.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
using namespace std;

int common( string a, string b )
{
   int counter = 0;
   for ( char c : "0123456789" ) counter += ( a.find( c ) != string::npos ) * ( b.find( c ) != string::npos );
   return counter;
}

int main()
{
   int A, B;
   cout << "Input A and B: ";
   cin >> A >> B;
   cout << "Number of digits in common = " << common( to_string( A ), to_string( B ) );
}




Stringify and use a set to count the unique characters.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <string>
#include <set>
using namespace std;

int uniq( string s )
{
   set<char> S( s.begin(), s.end() );
   return S.size();
}

int main()
{
   int A, B;
   cout << "Input A and B: ";
   cin >> A >> B;
   string sA = to_string( A ), sB = to_string( B );
   cout << "Number of digits in common = " << uniq( sA ) + uniq( sB ) - uniq( sA + sB );
}
Last edited on
If the standard library is to be used for this, the sensible choice would be std::bitset<10>:

1
2
3
4
5
6
7
8
9
10
11
#include <bitset>

static std::bitset<10> digits_in( unsigned long long number )
{
    std::bitset<10> bs( number == 0 ) ;
    for( ; number ; number /= 10 ) bs[ number%10 ] = true ;
    return bs ;
}

static std::size_t cnt_common_digits( unsigned long long m, unsigned long long n )
{ return ( digits_in(m) & digits_in(n) ).count() ; }

https://godbolt.org/g/g11tR9
Without the standard library then.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int isPresent( int n )
{
   int bits = 0;
   for ( ; n; n /= 10 ) bits = bits | 1 << (n%10);
   return bits;
}

int countBits( int b )
{
   int counter = 0;
   for ( ; b; b = b >> 1 ) counter += b & 1;
   return counter;
}

int main()
{
   int A, B;
   cout << "Input A and B: ";   cin >> A >> B;
   cout << "Number of digits in common = " << countBits( isPresent( A ) & isPresent( B ) );
}
This kind of assignment is not about being fancy. It is about being able to split a number into digits using division and remainder.

The assignment has an added trick: for each digit you find, keep track of whether or not it exists. This is a simple histogram trick.

Write yourself a function that fills a histogram with the number of times a digit appears (or even just if a digit appears, the number of times is not really important, only that it appeared).

void find_digits( int n, int digits[10] );

Now all you need to do is call the function for your two numbers, then compare the two histograms:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
  int a, b;
  int adigits[ 10 ] = { 0 };
  int bdigits[ 10 ] = { 0 };

  // (get a and b from user here)
  
  find_digits( a, adigits );
  find_digits( b, bdigits );

  // now just loop through the two arrays. When you find a non-zero pair, print it.
  for (int n = 0; n < 10; n++)
    if (adigits[ n ] && bdigits[ n ])
      ...

Hope this helps.
A lot o these are pretty good. I have one with a single loop (only as long as the longest number). Might be a little heavier cause of vectors, and because I arbitrarily filled one with all -1, and one with all -2, just to differentiate for the upcoming set intersection (not as fancy as dot products, etc). Left in some debug couts so you can see how it works.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Heavier, but perhaps more readable
int DigitsInCommon(int a, int b)
{
    vector<int> a_digits(10,-1);
    vector<int> b_digits(10,-2);
    int a_right = -1;
    int b_right = -1;
    int m = max(a,b);
    
    while (m!=0)    
    {
        if (a!=0)
        {
            a_right = a%10;
            a_digits[a_right] = a_right;
            a/=10;
        }
        if (b!=0)
        {
            b_right = b%10;
            b_digits[b_right] = b_right;
            b/=10;
        }        
        m/=10;        
    }
    std::vector<int> common_data;
    set_intersection(a_digits.begin(), a_digits.end(),
                     b_digits.begin(), b_digits.end(), 
                     std::back_inserter(common_data));
    
    /*
    cout << "\na_digits: ";
    for (int k=0; k<a_digits.size(); ++k)
      cout << a_digits[k]<<" ";
    cout << "\n";
       
    cout << "b_digits: ";
    for (int k=0; k<b_digits.size(); ++k)
      cout << b_digits[k]<<" ";
    cout << "\n";
    
    cout << "common_data: ";
    for (int k=0; k<common_data.size(); ++k)
      cout << common_data[k]<<" ";
    cout << "\n\n\n";
    */
    return common_data.size();
}

int main()
{
   int a=112358;
   int b=179881;  //179
   
   cout << "Number of digits in common = " << DigitsInCommon(a,b) << "\n";
}
It does not matter how often a digit occurs.

And thus, for example 2222 and 222222222 have exactly one digit in common.
you guys rock, thank you so much for the help....I am really new at c++ so I might ask lots of "silly" questions for the next few months or years.
There’s no such thing as a “silly” question. You’ll keep asking them as long as you are a programmer. Just, over time, there will be fewer people able to answer your questions.
Registered users can post here. Sign in or register to post.