Reduced Fractions Up to a Denominator

Medium

Given an integer limit, return every fraction strictly between 0 and 1 that is in lowest terms and whose denominator does not exceed limit. Write each fraction as a string "numerator/denominator", such as "3/4". Each value must appear exactly once, in its reduced form. The fractions may be returned in any order.

Example 1

limit=4 → ['1/2', '1/3', '1/4', '2/3', '3/4']

Denominators 2, 3 and 4 give 1/2, 1/3, 2/3, 1/4 and 3/4; 2/4 reduces to 1/2 and is not listed again.

Example 2

limit=2 → ['1/2']

The only fitting fraction is 1/2.

Example 3

limit=1 → []

With denominator 1 there is no fraction strictly between 0 and 1, so the list is empty.

Constraints

1 ≤ limit ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math String Number Theory

Similar problems

Even Vowel and Consonant Pieces Medium Balanced Stretches of a String Hard Largest Palindrome That Is a Multiple Hard Zero-Free Number With a Multiple Digit Product Hard Top of a Digit Pyramid Easy

Input

limit=4

Expected

['1/2', '1/3', '1/4', '2/3', '3/4']

Run checks the first 3 tests in your browser. Submit checks all 25 tests on the server, hidden ones included.