Statistics

Problem Statement for "MaximumScoredNumber"

Problem Statement

In her favorite Math class, Little Bonnie learned that some non-negative integers can be represented as the sum of the squares of two non-negative integers. For example, 13 can be represented as 2*2 + 3*3.

Bonnie later discovered that some of those integers can even be represented by more than one possible pair. For example, 25 can be represented as 0*0 + 5*5, and it can also be represented as 3*3 + 4*4.

She has defined the score of an integer as the number of different ways it can be represented as the sum of the squares of two non-negative integers. The order of the two squared integers is not important. In other words, a*a + b*b is equivalent to b*b + a*a, so they should only count once in the score. So, 25 has a score of 2, 2 has a score of 1 (2 = 1*1 + 1*1), 1 also has a score of 1 (1 = 0*0 + 1*1) and 3 has a score of 0.

Bonnie needs your help in solving the following problem. She wants to find the integer between lowerBound and upperBound, inclusive, with the maximum score. If multiple integers have the same highest score, return the largest among them.

Definition

Class:
MaximumScoredNumber
Method:
getNumber
Parameters:
int, int
Returns:
int
Method signature:
int getNumber(int lowerBound, int upperBound)
(be sure your method is public)

Constraints

  • upperBound will be between 0 and 10000, inclusive.
  • lowerBound will be between 0 and upperBound, inclusive.

Examples

  1. 0

    2

    Returns: 2

    In the range 0 to 2, the numbers have the following scores: 0 has a score of 1: 0 = 0*0 + 0*0 1 has a score of 1: 1 = 0*0 + 1*1 2 has a score of 1: 2 = 1*1 + 1*1 All of them have the same score. Number 2 is the biggest so it is returned.

  2. 0

    30

    Returns: 25

    25 is the only number between 0 and 30 having a score of 2.

  3. 0

    0

    Returns: 0

  4. 100

    101

    Returns: 100

  5. 5

    99

    Returns: 85

  6. 0

    10000

    Returns: 9425

  7. 0

    9424

    Returns: 5525

  8. 9424

    9424

    Returns: 9424

  9. 10000

    10000

    Returns: 10000

  10. 3

    3

    Returns: 3

  11. 5

    5000

    Returns: 4225

  12. 0

    5524

    Returns: 4225

  13. 1

    5525

    Returns: 5525

  14. 2393

    7971

    Returns: 5525

  15. 2205

    7829

    Returns: 5525

  16. 5737

    8673

    Returns: 8450

  17. 1048

    3787

    Returns: 3770

  18. 1109

    1577

    Returns: 1525

  19. 6457

    9047

    Returns: 8450

  20. 250

    1034

    Returns: 1025

  21. 1226

    8869

    Returns: 5525

  22. 321

    493

    Returns: 425

  23. 279

    7777

    Returns: 5525

  24. 861

    1846

    Returns: 1625

  25. 5986

    9251

    Returns: 8450

  26. 511

    3369

    Returns: 3250

  27. 1022

    2607

    Returns: 2465

  28. 738

    1375

    Returns: 1105

  29. 5191

    8700

    Returns: 5525

  30. 2639

    6681

    Returns: 5525

  31. 111

    1978

    Returns: 1885

  32. 3828

    4173

    Returns: 3965

  33. 2225

    6721

    Returns: 5525

  34. 50

    388

    Returns: 325

  35. 3638

    5815

    Returns: 5525

  36. 8080

    9351

    Returns: 8450

  37. 4275

    4589

    Returns: 4505

  38. 15

    41

    Returns: 25

  39. 212

    1902

    Returns: 1885

  40. 485

    2812

    Returns: 2665

  41. 4286

    7592

    Returns: 5525

  42. 1344

    4042

    Returns: 3965

  43. 3899

    6351

    Returns: 5525

  44. 3502

    5718

    Returns: 5525

  45. 1360

    2022

    Returns: 1885

  46. 825

    2236

    Returns: 2210

  47. 999

    3692

    Returns: 3625

  48. 3693

    9798

    Returns: 9425

  49. 36

    77

    Returns: 65

  50. 461

    1365

    Returns: 1105

  51. 718

    1069

    Returns: 1025

  52. 645

    9116

    Returns: 5525

  53. 443

    8870

    Returns: 5525

  54. 552

    791

    Returns: 725

  55. 5807

    6523

    Returns: 6500

  56. 627

    6343

    Returns: 5525

  57. 180

    2456

    Returns: 2405

  58. 762

    4437

    Returns: 4225

  59. 6216

    7542

    Returns: 7225

  60. 4309

    9302

    Returns: 5525

  61. 695

    746

    Returns: 725

  62. 590

    2991

    Returns: 2665

  63. 1281

    1373

    Returns: 1325

  64. 6042

    7784

    Returns: 7225

  65. 1382

    3548

    Returns: 3485

  66. 797

    1922

    Returns: 1885

  67. 319

    703

    Returns: 650

  68. 2932

    7635

    Returns: 5525

  69. 351

    2135

    Returns: 2125

  70. 2283

    2940

    Returns: 2665

  71. 1724

    3213

    Returns: 3145

  72. 1886

    3003

    Returns: 2665

  73. 407

    428

    Returns: 425

  74. 708

    2958

    Returns: 2665

  75. 40

    4395

    Returns: 4225

  76. 269

    317

    Returns: 305

  77. 1775

    4103

    Returns: 3965

  78. 5851

    8221

    Returns: 8125

  79. 4596

    9771

    Returns: 9425

  80. 6953

    8729

    Returns: 8450

  81. 3201

    3376

    Returns: 3250

  82. 3999

    8693

    Returns: 5525

  83. 3423

    5251

    Returns: 4225

  84. 4605

    7812

    Returns: 5525

  85. 1654

    3068

    Returns: 2665

  86. 1882

    3136

    Returns: 2665

  87. 8134

    8191

    Returns: 8177

  88. 3362

    3425

    Returns: 3425

  89. 5824

    9116

    Returns: 8450

  90. 1252

    4464

    Returns: 4225

  91. 1442

    4236

    Returns: 4225

  92. 168

    849

    Returns: 845

  93. 563

    5757

    Returns: 5525

  94. 1214

    1947

    Returns: 1885

  95. 571

    3805

    Returns: 3770

  96. 7544

    8831

    Returns: 8450

  97. 532

    1297

    Returns: 1105

  98. 2117

    7521

    Returns: 5525

  99. 1102

    4360

    Returns: 4225

  100. 4121

    5380

    Returns: 4225

  101. 1836

    6907

    Returns: 5525

  102. 4

    6

    Returns: 5

  103. 5028

    5080

    Returns: 5050

  104. 2278

    3841

    Returns: 3770

  105. 3152

    7151

    Returns: 5525

  106. 1261

    3025

    Returns: 2665

  107. 29

    92

    Returns: 85

  108. 222

    284

    Returns: 265

  109. 2507

    4222

    Returns: 3965

  110. 8325

    9112

    Returns: 8450

  111. 70

    1332

    Returns: 1105

  112. 1023

    8823

    Returns: 5525

  113. 5844

    7312

    Returns: 7225

  114. 60

    705

    Returns: 650

  115. 1090

    6142

    Returns: 5525

  116. 1194

    6145

    Returns: 5525

  117. 3899

    4379

    Returns: 4225

  118. 72

    5867

    Returns: 5525

  119. 2791

    4911

    Returns: 4225

  120. 1805

    7784

    Returns: 5525

  121. 115

    4189

    Returns: 3965

  122. 6850

    9163

    Returns: 8450

  123. 1677

    6868

    Returns: 5525

  124. 7340

    9137

    Returns: 8450

  125. 82

    740

    Returns: 725

  126. 269

    2164

    Returns: 2125

  127. 474

    1027

    Returns: 1025

  128. 922

    3333

    Returns: 3250

  129. 1903

    3497

    Returns: 3485

  130. 7625

    9758

    Returns: 9425

  131. 1315

    5057

    Returns: 4225

  132. 1638

    7035

    Returns: 5525

  133. 2150

    2771

    Returns: 2665

  134. 5

    84

    Returns: 65

  135. 72

    73

    Returns: 73

  136. 7

    7

    Returns: 7

  137. 25

    169

    Returns: 169

  138. 1

    9999

    Returns: 9425

  139. 20

    25

    Returns: 25

  140. 25

    30

    Returns: 25

  141. 0

    3

    Returns: 2

  142. 0

    16

    Returns: 16

  143. 24

    26

    Returns: 25

  144. 0

    8

    Returns: 8

  145. 9971

    9971

    Returns: 9971

  146. 1

    4

    Returns: 4

  147. 12

    13

    Returns: 13

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: