Last Updated: 15 Dec, 2020

Counting Pairs

Moderate

Asked in companies

Solve now

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.

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.

Solve now

Approaches

01 Approach

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).

Solve now

02 Approach

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)
Iterate over all possible values of Y, where N*N is divisible by Y - N, and we can find the corresponding X value. And subsequently, we will get the right pair of solutions. Increment the counter where N*N is divisible by Y-N will give us the required count of 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.

E.g. For N = 6, Y values will lie in the range(N+1, N*N+N) ie. in range(7, 42).

Now, Y-N will be factor N*N for Y values in the set {7, 8, 9, 10, 12, 15, 18, 24, 42}.

For Y values in this set, we can get corresponding X values as {42, 24, 18, 15, 12, 10, 9, 8, 7}. So we have 9 (X, Y) pairs for which the given equation can be satisfied.

Solve now

03 Approach

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)
Iterate over all the possible values of Y, where N*N is divisible by Y - N (not all possible Y values), and we can find the corresponding X value. And subsequently, we will get the right pair of solutions. Increment the counter where N*N is divisible by Y-N will give us the required count of pairs.
For ensuring Y must take only the values where N*N is divisible by Y - N, we can iterate over all the factors of N*N, and equating that factor with Y - N will give us the required Y values.
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.

E.g. For N = 6, Y values will lie in the range(N+1, N*N+N) ie. in range(7, 42).

Now, factors for N*N will be {1, 2, 3, 4, 6, 9, 12, 18, 36}. With the help of these factors, we can get Y values which is nothing but Factor + N. Hence required Y values will be {7, 8, 9, 10, 12, 15, 18, 24, 42} and corresponding X values will be

{42, 24, 18, 15, 12, 10, 9, 8, 7}. This way, we have 9 (X, Y) pairs that satisfy the given equation.

Solve now