CalcRoot | Topcoder Archive

Problem Statement

You are developing a new calculator with a square root function. To make things simple for your clients, you have decided to approximate square roots as simple fractions, rather than displaying a long sequence of digits.

You will be given N and D and should return the fraction closest to sqrt(N) for which the denominator is not greater than D. The fraction should be returned in the form "A/B" where A and B are positive integers with no common factors greater than one.

Definition

Class:: CalcRoot
Method:: approximate
Parameters:: int, int
Returns:: String
Method signature:: String approximate(int N, int D)
(be sure your method is public)

Constraints

N will be between 1 and 1000000, inclusive.
D will be between 1 and 1000, inclusive.

Examples

```
4
```
```
10
```
```
Returns: "2/1"
```
```
5
```
```
3
```
```
Returns: "7/3"
```
sqrt(5) = 2.236
```
12
```
```
10
```
```
Returns: "31/9"
```
sqrt(12) = 3.464
```
23743
```
```
763
```
```
Returns: "98462/639"
```

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.