NthFraction
TCCC05 Round 2 · 2005-01-10 · by lars2520
TCCC05 Round 2 · 2005-01-10 · by lars2520 · Advanced Math, Sorting
Problem Statement
Problem Statement
Given an int , bound, consider the infinite set of all reduced fractions whose numerator is a positive integer and whose denominator is a positive integer less than or equal to bound. Now, find the Nth smallest (indexed from 1) fraction and return it as a String in the form "a/b", with no leading zeros in either integer. See example 0 for further clarifications.
Notes
- A reduced fraction is one of the form a/b for which there is no integer g > 1 such that both a and b are divisible by g.
Constraints
- N will be between 1 and 2,000,000,000, inclusive.
- bound will be between 1 and 1000, inclusive.
Examples
0)
5 3 Returns: "4/3"
The ordered set of fractions is {1/3, 1/2, 2/3, 1/1, 4/3, 3/2, 5/3, ...}
1)
1000 100 Returns: "18/55"
2)
1 1000 Returns: "1/1000"
3)
502 1000 Returns: "2/999"
4)
2000000000 1000 Returns: "6377551/970"
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NthFraction with a public method string getFraction(int N, int bound) · 65 test cases · 2 s / 256 MB per case