Day 16 | Little Elephant and Numbers | C++

I like this problem a lot because we will learn how to find out the factors of an integer, and learn how to use maps as well.

The problem is pretty straightforward, as we need to

1. Find all divisors of x

2. Check with all divisors if they have any digit same digit as x

Let's dive into how we will be solving each part

Finding all divisors of x

Since x is up to 10^9, hence we cannot run a loop from 1 to x to find all the divisors.

But if you remember the trick that we discussed earlier in Sqrt Prime Check, if a divisor is greater than sqrt(x) then another will be less than it.

Hence, we can find all divisors by running a check-up to sqrt(x).

You can find all Divisors in O(Sqrt(X)) like this

vector<int> divisors;
for(int i = 1; i * i <= x; i++){
    if(x % i != 0) continue; // x is not divisble by i
    int factor_1 = i;
    int factor_2 = x / i;
    divisors.emplace_back(factor_1);
    if(factor_1 != factor_2){ // in case factor_1 * factor_1 = x
        divisors.emplace_back(factor_1);
    }
}

Checking if any divisor contains the same digit as x

We can check if the two numbers same contain the same digit by actually breaking up the number digit by digit and storing the frequency of the digit.

Then we check if there is any digit, for which frequency in both numbers is non-zero.

bool check_if_digits_same(int a, int b){
    map<int,int> dig_count_1, dig_count_2;
    while(a > 0){
        dig_count_1[a%10]++;
        a/=10;
    }
    while(b > 0){
        dig_count_2[b%10]++;
        b/=10;
    }
    for(int i = 0; i < 10; i++){
        if(dig_count_1[i] > 0 && dig_count_2[i] > 0){
            return true;
        }
    }
    return false;
}

You can find my implementation here.