Counting Pairs

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
11 upvotes
Asked in companies
GrowwAdobeThought Works

Problem statement

You are given a positive integer N and an equation 1/X + 1/Y = 1/N

You need to determine the count of all possible positive integral solutions (X, Y) for the above equation.

Note:

1. X and Y should be greater than 0.
2. (X, Y) and (Y, X) are considered different solutions if X is not equal to Y, i.e. (X, Y) and (Y, X) will not be distinct if X=Y.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer 'T' denoting the number of test cases.

The first and only line of each test case consists of a single positive integer 'N'.
Output Format: 
For each test case, print an integer that denotes the count of the number of pairs satisfying the equation in a new line.

The output of each test case should be printed in a separate line.
Note: 
You don't have to print anything. It has already been taken care of. Just Implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 10^4

Where 'T' is the number of test cases, and 'N' is the given integer.
Time Limit: 1 sec.
Sample Input 1:
1
5
Sample Output 1:
3
Explanation for sample input 1:
There are only 3 pairs satisfying the given equation { (6, 30), (10, 10), (30, 6) }.
Eg.  1/6  + 1/30 = 1/5, 1/10 + 1/10 = 1/5.
Sample Input 2:
1
6
Sample Output 2:
9
Explanation for sample input 2:
There are 6 pairs satisfying the given equation { (7, 42), (8, 24), (9, 18), (10, 15), (12, 12), (15, 10), (18, 9), (24, 8), (42, 7) }.
Eg.  1/7  + 1/42 = 1/6, 1/9 + 1/18 = 1/6.
Hint

Iterate over all possible values of (X, Y).

Approaches (3)
Naive Solution (Time limit Exceed)
  • Given equation can be simplified as follows:
    • 1/X + 1/Y = 1/N
    • 1/X = 1/N - 1/Y
    • 1/X = (Y - N)/(N*Y)
    • X = (N*Y)/(Y - N)
    • X = (N*Y - N*N + N*N)/(Y-N)
    • X = (N(Y-N) + N*N)/(Y-N)
    • X = N + (N*N)/(Y-N)
  • To identify the total number of pairs satisfying the given equation, iterate over all the possible values of X and Y and increment a counter, where current X and Y values satisfy the above equation.
  • This will give us the count of required pairs.
  • For finding the range of values Y may take, we can see that for an integral solution, N*N should be divisible by Y-N.
    • In the equation, the denominator should be non zero and Y > 0 therefore,
      • Y - N > 0.
      • Y > N.
    • So the smallest positive value that Y may take is N + 1.
    • Also, to get the integral value of X, the denominator should be less than or equal to the numerator, therefore,
      • Y - N <= N*N.
      • Y <= N*N + N.
    • So the highest positive value that Y may take is N*N + N.
  • Similarly, for X, its value also should lie in range (N + 1, N * N + N).
Time Complexity

O(N^4), where N is the given positive integer.

 

As X and Y may take values in the range N + 1 to N^2 + N, hence there are N^2 different values for X and Y. So the total number of pairs (X, Y) is of the order of N^4. 

Space Complexity

O(1).

 

We are using constant extra memory. 

Code Solution
(100% EXP penalty)
Counting Pairs
Full screen
Console