NthFraction | Topcoder Archive

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 N^th 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.

Definition

Class:: NthFraction
Method:: getFraction
Parameters:: int, int
Returns:: String
Method signature:: String getFraction(int N, int bound)
(be sure your method is public)

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

```
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, ...}
```
1000
```
```
100
```
```
Returns: "18/55"
```
```
1
```
```
1000
```
```
Returns: "1/1000"
```
```
1000000
```
```
1
```
```
Returns: "1000000/1"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.