Simplified Fractions

Easy
0/40
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in company
alibaba

Problem statement

You are given an integer ‘N’. Your task is to find all “simplified fractions” in the range [0, 1] whose denominator is less than or equal to ‘N’.

Note:

1. A “fraction” is not a whole number. It is a part of a whole.
2. When the numerator and denominator of a fraction are no longer to be reduced to any smaller number upon division by any common integer, the fraction is known as a “simplified fraction”. 
3. For example, 1/2 is a simplified fraction but 2/4 is not a simplified fraction as we can reduce 2/4 to 1/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 T test cases follow. 

The first and only line of each test case contains an integer, ‘N’, as described in the problem statement.
Output Format: 
For each test case, print the “list of strings representing all simplified fractions”, as described in the problem statement. If there are no such fractions, then print ‘-1’ without any quotes.

Output for each test case will be printed in a separate line.
Note: 
1. You do not need to print anything. It has already been taken care of. Just implement the given function.

2. You can return the list in “any order”.
Constraints: 
1 <= ‘T’ <= 10
1 <= ‘N’ <= 100

Time Limit: 1 sec
Sample Input 1:
1
3
Sample Output 1:
1/2 1/3 2/3
Explanation for sample input 1:
The only fractions 1/2, 1/3, and 2/3 satisfied all the conditions. ‘1/4’ is not a valid fraction in this case because the denominator must be less than or equal to the ‘3’.
Sample Input 2:
1
1
Sample Output 2:
-1
Explanation for sample input 2:
There are no valid fractions available whose denominator is less than or equal to ‘1’.
Hint

If the GCD of numerator and denominator is 1, then the fraction is simplified.

Approaches (1)
Brute-Force
  • First, let us try to understand the “simplified fraction”. If there are no such integers available that can divide both the numerator and denominator, then the fraction is called a simplified fraction. In other words, if the Greatest Common Divisor (GCD) of the numerator and the denominator is ‘1’, then the fraction is a “simplified fraction”.
  • Another condition is that we want the denominator to be less than or equal to ‘N’, and we know that to be a valid fraction the numerator must be less than the denominator.
  • This can conclude the logic part, what remains is only the implementation.


 

  • If 'N' == 1, then no valid fractions available. So, return “-1”.
  • Create an empty list to store the simplified fractions, let it be 'ANS'.
  • Run a loop from 'NUMERATOR' = 1 to 'NUMERATOR' < 'N', in each iteration:
    • Run a loop from 'DENOMINATOR' = 'NUMERATOR' + 1 to 'DENOMINATOR' <= 'N', in each iteration:
      • If the gcd('DENOMINATOR', 'NUMERATOR') == 1, then add a string “NUMERATOR/DENOMINATOR” to the 'ANS'.

Finally, return the 'ANS'.

Time Complexity

O((N^2)*(logN)), where ‘N’ is an integer given in the problem.

 

We are forming all fractions by using a nested for loop, and for each fraction, we are calculating the GCD, which will takes O(logN) time. So, the overall time complexity will be O(N^2*(logN)).

Space Complexity

O(N^2), where ‘N’ is an integer given in the problem.

 

As we are using a list to store the valid fractions. The size of the list is always to be less than N^2. Hence, the space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Simplified Fractions
Full screen
Console