Decimal | Topcoder Archive

Problem Statement

A rational number is a number which can be expressed as a ratio of two integers. In addition, all rational numbers can be expressed as a decimal number with some repeating periodic part (in some cases the repeating part is 0). For example 1/7 = 0.1428571428571428... with 142857 repeating itself infinitely. Other fractions have some finite number of non-repeating digits before the periodic part begins. For example, 1/6 = 0.166666... starts with a 1 and then settles into repeating 6's.

Your task is to write a class Decimal with a method find that takes four int's: lower, upper, lowerLength, and upperLength. Your method must find all integers n between lower and upper, inclusive, where the repeating portion of the decimal representation of 1/n has between lowerLength and upperLength digits, inclusive. You should return all of the numbers you find in a int[] sorted in increasing order.

Definition

Class:: Decimal
Method:: find
Parameters:: int, int, int, int
Returns:: int[]
Method signature:: int[] find(int lower, int upper, int lowerLength, int upperLength)
(be sure your method is public)

Constraints

lower and upper will be between 1 and 1000000, inclusive.
upper will be greater than or equal to lower.
The difference between upper and lower will be at most 100.
lowerLength and upperLength will be between 1 to 1000000, inclusive.
upperLength will be greater than or equal to lowerLength.

Examples

```
1
```
```
10
```
```
1
```
```
1
```
```
Returns: { 1,  2,  3,  4,  5,  6,  8,  9,  10 }
```
1/1 = 1.00000... 1/2 = 0.50000... 1/3 = 0.33333... 1/4 = 0.25000... 1/5 = 0.20000... 1/6 = 0.16666... 1/8 = 0.12500... 1/9 = 0.11111... 1/10 = 0.10000... Thus, all of the numbers other than 7 eventually settle into a repeating sequence of exactly 1 digit.
```
55
```
```
56
```
```
1
```
```
10
```
```
Returns: { 55,  56 }
```
1/55 = 0.01818... (18 is repeating) 1/56 = 0.017857142857142... (857142 is repeating) Both of these numbers have between 1 and 10 digits in its repeating part.

Returns: { 204,  209,  212,  228,  237,  247,  248,  255,  265,  266,  272,  279,  285 }

```
999983
```
```
999983
```
```
999982
```
```
999982
```
```
Returns: { 999983 }
```
The repeating part of 1/999983 is 999982 digits long!

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.