C++

Forum

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

barry23 (14)
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.
closed account (E0p9LyTq)
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
JLBorges (13770)
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.
lastchance (6980)
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
JLBorges (13770)
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
lastchance (6980)
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 ) );
}
Duthomhas (13201)
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.
icy1 (596)
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";
}
keskiverto (10399)
It does not matter how often a digit occurs.

And thus, for example 2222 and 222222222 have exactly one digit in common.
barry23 (14)
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.
Duthomhas (13201)
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.
Topic archived. No new replies allowed.