TheSimilarNumbers | Topcoder Archive

Problem Statement

Two positive integers A and B are called similar if A <= 10*B and B <= 10*A. For example, 1 and 10 are similar, but 1 and 11 are not.

You are given ints lower and upper. You must select as many integers as possible so that:

each selected integer is between lower and upper, inclusive;
no two selected integers are similar.

Return the maximum number of selected integers.

Definition

Class:: TheSimilarNumbers
Method:: find
Parameters:: int, int
Returns:: int
Method signature:: int find(int lower, int upper)
(be sure your method is public)

Constraints

upper will be between 1 and 1,000,000, inclusive.
lower will be between 1 and upper, inclusive.

Examples

```
1
```
```
10
```
```
Returns: 1
```
Any two integers between 1 and 10 are similar. Therefore you may select only 1 number.
```
5
```
```
511
```
```
Returns: 3
```
You can select 51, 5, and 511.
```
5
```
```
4747
```
```
Returns: 3
```
```
1
```
```
1000000
```
```
Returns: 6
```
```
10
```
```
10110
```
```
Returns: 3
```

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.