Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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 <= 100Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
2
3
4
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1447: Simplified Fractions
class Solution {
public List<String> simplifiedFractions(int n) {
List<String> ans = new ArrayList<>();
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j < n + 1; ++j) {
if (gcd(i, j) == 1) {
ans.add(i + "/" + j);
}
}
}
return ans;
}
private int gcd(int a, int b) {
return b > 0 ? gcd(b, a % b) : a;
}
}
// Accepted solution for LeetCode #1447: Simplified Fractions
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)
}
# Accepted solution for LeetCode #1447: Simplified Fractions
class Solution:
def simplifiedFractions(self, n: int) -> List[str]:
return [
f'{i}/{j}'
for i in range(1, n)
for j in range(i + 1, n + 1)
if gcd(i, j) == 1
]
// Accepted solution for LeetCode #1447: Simplified Fractions
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
}
}
// Accepted solution for LeetCode #1447: Simplified Fractions
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);
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.