A Number Game

Moderate
0/80
profile
Contributed by
1 upvote
Asked in company
Google inc

Problem statement

Ninja has an integer 'A'.

He will go through all integers 'X' from 1 to 10^18 and for every 'X', he will store the value of 'LCM(X,A) ÷ X'.

He wants to know the number of unique values he will obtain in the end.

Example : 
‘A’ = '2'
For X = 1, Ninja will get LCM(1,2) ÷ 1 = 2/1 = 2.
For X = 2, Ninja will get LCM (2,2) ÷ 2 = 2/2 = 1.
For X = 3, Ninja will get LCM (3,2) ÷ 3  = 6/3 = 2.
For X = 4, Ninja will get LCM (4,2) ÷ 4 = 4/2 = 2.
For X = 5, Ninja will get LCM (5,2) ÷ 5 = 10/2 = 2.
For X = 6, Ninja will get LCM (6,2) ÷ 6 = 6/6 = 1.
And so on, It can be verified that Ninja will never get any integer other than 1 and 2. Hence the answer for 'A' = 2 is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer 'A'.
Output format : 
For each test case, output the number of unique integers obtained for the function provided in the problem statement.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 ≤ T ≤ 10 
0 ≤ A ≤ 10^10

Time Limit: 1 sec
Sample Input 1 :
2
1
3
Sample Output 1 :
1
2
Explanation Of Sample Input 1 :
For 'A' =1, the LCM of '(X,1)' (1 <=X <= 10^18) is always X. Hence, we will always obtain the same integer (X/X) = 1.

For 'A' = 3,
For X = 1, Ninja will get LCM(1,3) ÷ 1 = 3/1 = 3.
For X = 2, Ninja will get LCM (2,3) ÷ 2 = 6/2 = 3.
For X = 3, Ninja will get LCM (3,3) ÷ 3  = 3/3 = 1.
For X = 4, Ninja will get LCM (4,3) ÷ 4 =  12/4 = 3.
For X = 5, Ninja will get LCM (5,3) ÷ 5 = 15/5 = 3.
For X = 6, Ninja will get LCM (6,3) ÷ 6 = 6/6 = 1.
And so on, It can be verified that Ninja will never get any integer other than 1 and 3. Hence the answer for 'A' = 3 is 2.
Sample Input 2 :
2
171
172
Sample Output 2 :
6
6
Hint

What is the maximum integer that can be obtained from doing the given operation?

Approaches (1)
Optimal

Approach :


 

  • For two (positive) integers 'X' and 'A', the properties of their greatest common divisor gcd and the least common multiple lcm come in pairs; the phenomenon is partly explained by the formula 'GCD(X, A)' × 'LCM(X, A)' = 'X' × 'A'.
  • Rearranging, 'LCM(X,A) ÷ X' = 'A ÷ GCD(X,A)'.
  • 'GCD(X,A)' can have minimum value of 1, so the maximum value of the equation will be 'A'.
  • 'GCD(X,A)' can have a maximum value 'A' (as 'A' <= 10^18), hence the minimum value of the equation will be 'A ÷A' = 1.
  • Now, for all values of  'X', 'GCD(X,A)' are either divisors of 'A' or multiples of divisors of ‘A’. Hence the unique integers than can be obtained is simply the number of divisors of 'A'. So the problem boils down to finding the number of divisors of 'A'.




 

Algorithm:


 

  • Initialize an integer variable 'count' to store the number of divisors of 'A'.
  • Iterate using variable 'i' from '1' to 'i * i' <= 'A'.
    • if('i' * 'i' == 'A'), we increment our 'count' by '1' since both the factors of the pair ('i' and 'A/i') are same.
    • Otherwise if (  'A%i' == 0 ), we increment our 'count' by 2, since both the factors ('i' and 'A/i') are distinct.
  • Return 'count'.
Time Complexity

O( sqrt(A) ). 


Since we run a loop from 1 to square root of 'A', the time complexity is of the order 
O( sqrt(A) ). 

Space Complexity

O(1)


 

Since we are using only constant extra space, the space complexity is O(1).

Code Solution
(100% EXP penalty)
A Number Game
Full screen
Console