Is Simplified Fractions easy or hard?

Simplified Fractions is generally considered an easy-to-medium math problem. The implementation is straightforward once you recognize that a fraction is simplified when the numerator and denominator are coprime, which you can verify using the GCD algorithm.

Simplified Fractions Python/Java solution

In Python or Java, loop over denominators from 2 to n and numerators from 1 to denominator−1. Compute gcd(a, b); if it equals 1, append the formatted string "a/b" to the result list. Both languages provide efficient built-in or standard-library GCD implementations.

How to solve Simplified Fractions in O(n)?

Generating every simplified fraction cannot be done in strict O(n) time because the number of valid fractions itself grows roughly on the order of n². However, Euler’s Totient Function can compute how many simplified fractions exist for each denominator in O(n log log n) preprocessing time, though you still need enumeration to list them.

What is the best approach for Simplified Fractions?

The most practical approach iterates every numerator and denominator pair where 1 ≤ numerator < denominator ≤ n and keeps the fraction only when gcd(numerator, denominator) = 1. Euclid's algorithm makes the GCD check efficient, giving an overall time complexity of O(n² log n). This solution is simple and is the one typically expected in coding interviews.

Is Simplified Fractions asked at Google/Amazon/Meta?

Problems involving coprime numbers, GCD, and fraction reduction frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts—Euclid’s algorithm and number theory reasoning—are commonly tested.

What data structure is used in Simplified Fractions?

No advanced data structure is required. The solution mainly uses nested iteration and the GCD function from number theory. Results are stored in a list of strings representing fractions such as "a/b".

What is the time complexity of Simplified Fractions?

The common solution runs in O(n² log n) time. There are about n²/2 numerator–denominator pairs to examine, and each pair requires a GCD computation that takes O(log n) using Euclid’s algorithm. Space complexity is O(1) excluding the output list of fractions.

Description Hints 2 Solution Video 12:36

1447. Simplified Fractions

Q: Is Simplified Fractions asked at Google/Amazon/Meta?

Problems involving coprime numbers, GCD, and fraction reduction frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, the underlying concepts—Euclid’s algorithm and number theory reasoning—are commonly tested.

Q: What data structure is used in Simplified Fractions?

No advanced data structure is required. The solution mainly uses nested iteration and the GCD function from number theory. Results are stored in a list of strings representing fractions such as "a/b".

Q: What is the time complexity of Simplified Fractions?

The common solution runs in O(n² log n) time. There are about n²/2 numerator–denominator pairs to examine, and each pair requires a GCD computation that takes O(log n) using Euclid’s algorithm. Space complexity is O(1) excluding the output list of fractions.

Medium70.3% acceptance1 company

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. You can return the answer in any order.

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".

Constraints:

1 <= n <= 100

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

A fraction is fully simplified if there is no integer that divides cleanly into the numerator and denominator.

Hint 2

In other words the greatest common divisor of the numerator and the denominator of a simplified fraction is 1.

12:36

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def simplifiedFractions(self, n: int) -> List[str]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution