TheSimilarNumbers
SRM 568 · 2012-12-13 · by ltaravilse
SRM 568 · 2012-12-13 · by ltaravilse · Simple Math
Problem Statement
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 givenint s lower and upper. You must select as many integers as possible so that:
You are given
- each selected integer is between lower and upper, inclusive;
- no two selected integers are similar.
Constraints
- upper will be between 1 and 1,000,000, inclusive.
- lower will be between 1 and upper, inclusive.
Examples
0)
1 10 Returns: 1
Any two integers between 1 and 10 are similar. Therefore you may select only 1 number.
1)
5 511 Returns: 3
You can select 51, 5, and 511.
2)
5 4747 Returns: 3
3)
1 1000000 Returns: 6
4)
10 10110 Returns: 3
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheSimilarNumbers with a public method int find(int lower, int upper) · 77 test cases · 2 s / 256 MB per case