HackerRank Number Theory – Easy math

Challenge: Easy math

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464753959

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/easy-math/problem

Cerinta

Charlie and Johnny play a game. For every integer *X* Charlie gives, Johnny has to find the smallest positive integer *Y*, such that X * Y contains only 4's and 0's and starts with one or more 4's followed by zero or more 0's. (i.e.), 404 is an invalid number but 400 is a valid number. 

If *a* is the number of 4's and *b* is the number of 0's, can you print the value of 2 * a + b.

**Input Format**<br>
The first line contains an integer T. T lines follow, each line containing the integer X as stated above.

**Output Format**<br>
For every X, print the output 2 * a + b in a newline as stated in the problem statement. 

**Constraints**<br>
1<=T<=10<sup>3</sup>  
1<=X<=10<sup>5</sup>

**Sample Input #00**
 
    3
    4
    5
    80

**Sample Output #00**
 
    2
    3
    4

**Explanation**  
For the 1<sup>st</sup> test-case, the smallest such multiple of 4 is **4** itself. Hence value of a will be 1 and and value of b will be 0. The required value of 2 * a+b is 2.     

For the 2<sup>nd</sup> test-case, **Y** = 8 and 40 is the minimum such multiple of 5. Hence value of a,b and 2 * a+b will be 1, 1 and 3 respectively.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;

    unordered_map<int,int> memo;
    memo.reserve(1 << 15);

    while (T--) {
        int X;
        cin >> X;

        int x = X;
        int v2 = 0, v5 = 0;
        while (x % 2 == 0) {
            x /= 2;
            ++v2;
        }
        while (x % 5 == 0) {
            x /= 5;
            ++v5;
        }

        int a;
        if (x == 1) {
            a = 1;
        } else {
            auto it = memo.find(x);
            if (it != memo.end()) {
                a = it->second;
            } else {
                int rem = 0;
                a = 0;
                do {
                    rem = (rem * 10 + 1) % x;
                    ++a;
                } while (rem != 0);
                memo[x] = a;
            }
        }

        int b = max(v5, max(0, v2 - 2));
        long long ans = 2LL * a + b;
        cout << ans << '\n';
    }

    return 0;
}