Simplified Fractions solution and explanation
Google
9 more videos on this problem
LeetCode 1447: Simplified FractionsKnowledge Center · 12:36 · 2K views
Simplified FractionsFraz · 8:35 · 628 views
simplified fractions | simplified fractions leetcode | leetcode 1447 | math gcdNaresh Gupta · 4:27 · 269 views
1447. Simplified Fractions | LeetcodeChhavi Bansal · 10:55 · 215 views
1447. Simplified Fractions (Leetcode Medium)Programming Live with Larry · 3:07 · 140 views
1447 Simplified Fractions || Biweekly Contest 26 || LEETCODE || C++ SOLUTIONcode Explainer · 3:57 · 118 views
Leetcode 1447 Simplified FractionsMaxMing · 2:47 · 71 views
Simplified Fractions (Leetcode 1447)Coding Interviews · 24:57 · 62 views
1447. Simplified Fractions | Leetcode | DSA Hindi | JAVAThis Is The Way · 12:36 · 35 views
LeetCode | Solved in 6:22 mins | EP88 | 1447. Simplified FractionsEduardo Nakanishi · 6:22 · 11 views
The problem
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
Approach overview
Problem Overview: Given an integer n, return all fractions between 0 and 1 with denominators less than or equal to n that are already in their simplified form. A fraction a/b is valid only if 1 ≤ a < b ≤ n and gcd(a, b) = 1.
Approach 1: Brute Force with GCD Check (Time: O(n² log n), Space: O(1) excluding output)
Iterate over every possible denominator b from 2 to n. For each denominator, iterate the numerator a from 1 to b - 1. The fraction is simplified only when gcd(a, b) = 1. Use Euclid's algorithm to compute the GCD and append the string representation "a/b" to the result when the condition holds. The key insight: a fraction is already simplified exactly when numerator and denominator share no common divisor other than 1.
This approach directly models the definition of reduced fractions. You perform roughly n(n-1)/2 checks, and each GCD computation takes O(log n). The algorithm is simple, reliable, and works well within constraints. It relies on concepts from math and number theory.
Approach 2: Using Euler's Totient Function (Time: O(n log log n + n²), Space: O(n))
Euler's Totient Function φ(b) gives the number of integers in [1, b] that are coprime with b. For each denominator b, exactly φ(b) valid simplified fractions exist. You can precompute totients for all values up to n using a sieve-style method in O(n log log n) time.
Once the totient values are available, iterate through numerators and keep those that are coprime with the denominator. The totient insight helps reason about how many fractions should appear for each denominator and connects the problem to deeper number theory properties. This method is mostly educational here since we still enumerate candidate numerators, but the totient precomputation can be reused in other problems involving coprime counts.
Recommended for interviews: The brute force with GCD check is the expected solution. It shows you understand the mathematical definition of simplified fractions and can apply Euclid’s algorithm efficiently. Mentioning Euler’s Totient Function demonstrates stronger number theory knowledge, but interviewers typically look for the clean GCD-based enumeration.
Approach 1: Brute Force with GCD Check
This approach involves iterating over all possible denominators and numerators and checking if each pair is coprime using the gcd (greatest common divisor) function. If gcd(numerator, denominator) is 1, the fraction is simplified.
from math import gcd
def simplified_fractions(n):
result = []
for denom in range(2, n + 1):
for num in range(1, denom):
if gcd(num, denom) == 1:
result.append(f"{num}/{denom}")
return resultimport java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> simplifiedFractions(int n) {
List<String> result = new ArrayList<>();
for (int denom = 2; denom <= n; denom++) {
for (int num = 1; num < denom; num++) {
if (gcd(num, denom) == 1) {
result.add(num + "/" + denom);
}
}
}
return result;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}#include <iostream>
#include <vector>
#include <string>
#include <numeric>
std::vector<std::string> simplifiedFractions(int n) {
std::vector<std::string> result;
for (int denom = 2; denom <= n; ++denom) {
for (int num = 1; num < denom; ++num) {
if (std::gcd(num, denom) == 1) {
result.push_back(std::to_string(num) + "/" + std::to_string(denom));
}
}
}
return result;
}function simplifiedFractions(n) {
const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);
const result = [];
for (let denom = 2; denom <= n; denom++) {
for (let num = 1; num < denom; num++) {
if (gcd(num, denom) === 1) {
result.push(`${num}/${denom}`);
}
}
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
char** simplifiedFractions(int n, int* returnSize) {
char** result = (char**)malloc(sizeof(char*) * 5000);
*returnSize = 0;
for (int denom = 2; denom <= n; denom++) {
for (int num = 1; num < denom; num++) {
if (gcd(num, denom) == 1) {
result[*returnSize] = (char*)malloc(sizeof(char) * 10);
sprintf(result[*returnSize], "%d/%d", num, denom);
(*returnSize)++;
}
}
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<string> SimplifiedFractions(int n) {
var result = new List<string>();
for (int denom = 2; denom <= n; denom++) {
for (int num = 1; num < denom; num++) {
if (GCD(num, denom) == 1) {
result.Add($"{num}/{denom}");
}
}
}
return result;
}
private int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
}This solution uses two nested loops to iterate through every possible fraction with a denominator less than or equal to n. The gcd function is used to determine if the numerator and denominator are coprime.
Time Complexity: O(n^2 * log(m)), where n is the input number and m is the larger number between the numerator and denominator, because calculating gcd takes O(log(m)).
Space Complexity: O(1) for storing results, not considering the output list.
Approach 2: Using Euler's Totient Function
The fractions can also be generated using Euler's Totient Function, which calculates the number of integers up to a given integer that are coprime with it. This approach can be more efficient for certain applications but is complex to implement without specific libraries or integer properties handling in mind.
from math import gcd
def euler_totient_phi(n):
phi = [0] * (n + 1)
for i in range(1, n + 1):
phi[i] = i
for p in range(2, n + 1):
if phi[p] == p: # p is a prime number
for k in range(p, n + 1, p):
phi[k] *= (p - 1)
phi[k] //= p
return phi
def simplified_fractions(n):
phi = euler_totient_phi(n)
result = []
for denom in range(2, n + 1):
for num in range(1, denom):
if gcd(num, denom) == 1:
result.append(f"{num}/{denom}")
return resultThis solution uses Euler's Totient Function to precompute the number of integers that are coprime with each possible denominator. It maintains the previous gcd-check logic to generate simplified fractions.
Time Complexity: O(n * log(log n)) due to totient calculation + O(n^2) for iterating fractions.
Space Complexity: O(n) for storing the totient values.
Approach 3: Default Approach
function simplifiedFractions(n: number): string[] {
const ans: string[] = [];
for (let i = 1; i < n; ++i) {
for (let j = i + 1; j < n + 1; ++j) {
if (gcd(i, j) === 1) {
ans.push(`${i}/${j}`);
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func simplifiedFractions(n int) (ans []string) {
for i := 1; i < n; i++ {
for j := i + 1; j < n+1; j++ {
if gcd(i, j) == 1 {
ans = append(ans, strconv.Itoa(i)+"/"+strconv.Itoa(j))
}
}
}
return ans
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}impl Solution {
fn gcd(a: i32, b: i32) -> i32 {
match b {
0 => a,
_ => Solution::gcd(b, a % b),
}
}
pub fn simplified_fractions(n: i32) -> Vec<String> {
let mut res = vec![];
for i in 1..n {
for j in i + 1..=n {
if Solution::gcd(i, j) == 1 {
res.push(format!("{}/{}", i, j));
}
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force with GCD Check | Time Complexity: O(n^2 * log(m)), where n is the input number and m is the larger number between the numerator and denominator, because calculating gcd takes O(log(m)). |
| Using Euler's Totient Function | Time Complexity: O(n * log(log n)) due to totient calculation + O(n^2) for iterating fractions. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with GCD Check | O(n² log n) | O(1) | Standard solution for interviews. Directly checks if numerator and denominator are coprime. |
| Euler's Totient Function Insight | O(n log log n + n²) | O(n) | Useful when studying number theory or when totient values are reused in multiple computations. |
Frequently asked questions
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.