Statistics

Problem Statement for "TheSimilarNumbers"

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. 1

    10

    Returns: 1

    Any two integers between 1 and 10 are similar. Therefore you may select only 1 number.

  2. 5

    511

    Returns: 3

    You can select 51, 5, and 511.

  3. 5

    4747

    Returns: 3

  4. 1

    1000000

    Returns: 6

  5. 10

    10110

    Returns: 3

  6. 1

    1

    Returns: 1

  7. 1000000

    1000000

    Returns: 1

  8. 491273

    842398

    Returns: 1

  9. 849859

    958925

    Returns: 1

  10. 67803

    771363

    Returns: 2

  11. 184892

    391907

    Returns: 1

  12. 75799

    256150

    Returns: 1

  13. 268944

    342402

    Returns: 1

  14. 228640

    894352

    Returns: 1

  15. 903885

    908656

    Returns: 1

  16. 292588

    414271

    Returns: 1

  17. 852057

    889141

    Returns: 1

  18. 73955

    739551

    Returns: 2

  19. 73955

    739550

    Returns: 1

  20. 40363

    403631

    Returns: 2

  21. 40363

    403630

    Returns: 1

  22. 14367

    143671

    Returns: 2

  23. 14367

    143670

    Returns: 1

  24. 844

    84411

    Returns: 3

  25. 844

    84410

    Returns: 2

  26. 6646

    664611

    Returns: 3

  27. 6646

    664610

    Returns: 2

  28. 937

    93711

    Returns: 3

  29. 937

    93710

    Returns: 2

  30. 883

    883111

    Returns: 4

  31. 883

    883110

    Returns: 3

  32. 842

    842111

    Returns: 4

  33. 842

    842110

    Returns: 3

  34. 314

    314111

    Returns: 4

  35. 314

    314110

    Returns: 3

  36. 74

    741111

    Returns: 5

  37. 74

    741110

    Returns: 4

  38. 14

    141111

    Returns: 5

  39. 14

    141110

    Returns: 4

  40. 53

    531111

    Returns: 5

  41. 53

    531110

    Returns: 4

  42. 4

    411111

    Returns: 6

  43. 4

    411110

    Returns: 5

  44. 6

    611111

    Returns: 6

  45. 6

    611110

    Returns: 5

  46. 2

    211111

    Returns: 6

  47. 2

    211110

    Returns: 5

  48. 2

    20

    Returns: 1

  49. 100000

    100000

    Returns: 1

  50. 2

    2

    Returns: 1

  51. 1

    11

    Returns: 2

  52. 1

    8

    Returns: 1

  53. 5

    5

    Returns: 1

  54. 1

    9

    Returns: 1

  55. 2

    4

    Returns: 1

  56. 10

    101

    Returns: 2

  57. 1

    11122

    Returns: 5

  58. 55

    1000000

    Returns: 5

  59. 5

    51

    Returns: 2

  60. 6

    6

    Returns: 1

  61. 10

    10

    Returns: 1

  62. 500

    1500

    Returns: 1

  63. 2

    204

    Returns: 2

  64. 1

    99999

    Returns: 5

  65. 3

    11

    Returns: 1

  66. 10

    11

    Returns: 1

  67. 6

    7

    Returns: 1

  68. 5

    510

    Returns: 2

  69. 1

    111

    Returns: 3

  70. 5

    500

    Returns: 2

  71. 10

    100

    Returns: 1

  72. 6

    611

    Returns: 3

  73. 1

    110

    Returns: 2

  74. 4

    411

    Returns: 3

  75. 5000

    5000

    Returns: 1

  76. 1

    11111

    Returns: 5

  77. 1

    2

    Returns: 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.
This problem was used for: