Statistics

Problem Statement for "MagicCandy"

Problem Statement

Today is the Christmas Eve. People around the world celebrate this holiday. The following story takes place in the land of reindeer, where Santa Claus resides.


The reindeer love candies. They have n pieces of candy. The pieces of candy are numbered 1 through n. Dasher is one of the reindeer. He wants to eat one of the candies. To pick the one he will eat, Dasher uses the following method:
  • While there is more than one piece of candy:
  • Discard all candies that are numbered by perfect squares (i.e., candies 1, 4, 9, 16, 25, etc.).
  • Relabel the remaining k candies 1 through k, keeping the numbers in the same order.
  • Once only one piece of candy remains, Dasher will eat it.



You are given an int n. Your method must compute and return the number initially assigned to the piece of candy eaten by Dasher.

Definition

Class:
MagicCandy
Method:
whichOne
Parameters:
int
Returns:
int
Method signature:
int whichOne(int n)
(be sure your method is public)

Notes

  • It can be proved that Dasher's method will always lead to a situation in which only one piece of candy remains.

Constraints

  • n will be between 1 and 1,000,000,000 inclusive.

Examples

  1. 5

    Returns: 5

    We start with 5 candies. Let's call them A, B, C, D, and E. Initially, they are numbered 1 through 5, in this order. In the first round, we discard candies with numbers 1 (which is A) and 4 (which is D). This leaves us with candies B, C, and E. These candies now get new numbers: B becomes 1, C becomes 2, and E becomes 3. In the second round, we discard candy number 1 (which is now B). This leaves us with candies C and E. Again, the candies now get new numbers: C becomes 1 and E becomes 2. In the third round, we discard candy number 1 (which is now C). The only remaining candy is E. Its number in the beginning was 5, therefore our method should return 5.

  2. 9

    Returns: 7

    This time we start with 9 pieces of candy. If we label them A through I, the process will look as follows: start: ABCDEFGHI throw away candies 1, 4, 9 (A, D, I) after the first round: BCEFGH throw away candies 1, 4 (B, F) after the second round: CEGH throw away candies 1, 4 (C, H) after the third round: EG throw away candy 1 (E) at the end: G

  3. 20

    Returns: 17

  4. 5265

    Returns: 5257

  5. 20111223

    Returns: 20110741

  6. 1

    Returns: 1

  7. 977

    Returns: 962

  8. 999

    Returns: 993

  9. 407

    Returns: 401

  10. 655

    Returns: 651

  11. 819

    Returns: 813

  12. 717

    Returns: 703

  13. 201

    Returns: 197

  14. 773

    Returns: 757

  15. 354

    Returns: 343

  16. 525

    Returns: 507

  17. 279

    Returns: 273

  18. 172

    Returns: 170

  19. 103

    Returns: 101

  20. 473

    Returns: 463

  21. 50

    Returns: 50

  22. 991

    Returns: 962

  23. 446

    Returns: 442

  24. 592

    Returns: 577

  25. 226

    Returns: 226

  26. 496

    Returns: 485

  27. 954

    Returns: 931

  28. 611

    Returns: 601

  29. 722

    Returns: 703

  30. 361

    Returns: 343

  31. 254

    Returns: 241

  32. 736

    Returns: 730

  33. 426

    Returns: 421

  34. 443

    Returns: 442

  35. 869

    Returns: 842

  36. 587

    Returns: 577

  37. 19

    Returns: 17

  38. 419

    Returns: 401

  39. 20

    Returns: 17

  40. 648

    Returns: 626

  41. 335

    Returns: 325

  42. 72

    Returns: 65

  43. 251

    Returns: 241

  44. 674

    Returns: 651

  45. 239

    Returns: 226

  46. 919

    Returns: 901

  47. 631434

    Returns: 631231

  48. 573880

    Returns: 573807

  49. 218681

    Returns: 218557

  50. 81607

    Returns: 81511

  51. 184094

    Returns: 184042

  52. 41130

    Returns: 41007

  53. 212195

    Returns: 212061

  54. 841452

    Returns: 840890

  55. 716519

    Returns: 715717

  56. 32472

    Returns: 32401

  57. 949657

    Returns: 949651

  58. 565925

    Returns: 565505

  59. 830725

    Returns: 829922

  60. 280746

    Returns: 280371

  61. 651694

    Returns: 651250

  62. 601368

    Returns: 600626

  63. 536028

    Returns: 535825

  64. 19751

    Returns: 19741

  65. 771447

    Returns: 770885

  66. 772625

    Returns: 771763

  67. 216981

    Returns: 216691

  68. 710335

    Returns: 709807

  69. 979921

    Returns: 979111

  70. 179520

    Returns: 179353

  71. 13661

    Returns: 13573

  72. 259393

    Returns: 259082

  73. 292057

    Returns: 291601

  74. 526906

    Returns: 526351

  75. 21284

    Returns: 21171

  76. 690533

    Returns: 689731

  77. 996785

    Returns: 996005

  78. 898420

    Returns: 897757

  79. 106526

    Returns: 106277

  80. 86403

    Returns: 86143

  81. 498306

    Returns: 497731

  82. 645900

    Returns: 645613

  83. 880133

    Returns: 879845

  84. 392602

    Returns: 392503

  85. 961461

    Returns: 961381

  86. 42176

    Returns: 42026

  87. 139493627

    Returns: 139487911

  88. 105126837

    Returns: 105124010

  89. 460216916

    Returns: 460209757

  90. 685443914

    Returns: 685418581

  91. 792615630

    Returns: 792591410

  92. 702309530

    Returns: 702303002

  93. 841851564

    Returns: 841841211

  94. 444959509

    Returns: 444956837

  95. 489967884

    Returns: 489958226

  96. 61948395

    Returns: 61944771

  97. 31483581

    Returns: 31483322

  98. 358620543

    Returns: 358609970

  99. 99898192

    Returns: 99890031

  100. 71209241

    Returns: 71208283

  101. 166207090

    Returns: 166203665

  102. 525732570

    Returns: 525716113

  103. 84501369

    Returns: 84492865

  104. 382893046

    Returns: 382887057

  105. 384179516

    Returns: 384160001

  106. 573649693

    Returns: 573626451

  107. 702770728

    Returns: 702753591

  108. 13275450

    Returns: 13275093

  109. 288437904

    Returns: 288422290

  110. 115200608

    Returns: 115197290

  111. 145668933

    Returns: 145660762

  112. 331963137

    Returns: 331950181

  113. 16264807

    Returns: 16261057

  114. 368394082

    Returns: 368390443

  115. 391420538

    Returns: 391406657

  116. 638670155

    Returns: 638648713

  117. 649752508

    Returns: 649740101

  118. 446313987

    Returns: 446307877

  119. 172134326

    Returns: 172121281

  120. 543125116

    Returns: 543123026

  121. 674531602

    Returns: 674518813

  122. 218048458

    Returns: 218034757

  123. 513753516

    Returns: 513747557

  124. 783235033

    Returns: 783216197

  125. 927116012

    Returns: 927111153

  126. 987718240

    Returns: 987687757

  127. 1000000000

    Returns: 999982507

  128. 998987654

    Returns: 998970843

  129. 555555555

    Returns: 555544901

  130. 999998797

    Returns: 999982507

  131. 999982506

    Returns: 999950885

  132. 987654321

    Returns: 987624903

  133. 999999999

    Returns: 999982507

  134. 99999545

    Returns: 99990001

  135. 999982507

    Returns: 999982507

  136. 100000000

    Returns: 99990001

  137. 999982508

    Returns: 999982507

  138. 999999998

    Returns: 999982507

  139. 900000000

    Returns: 899970001

  140. 999999996

    Returns: 999982507

  141. 27

    Returns: 26

  142. 999980884

    Returns: 999950885

  143. 99999

    Returns: 99857

  144. 12896

    Returns: 12883

  145. 3

    Returns: 3

  146. 10

    Returns: 10

  147. 257000001

    Returns: 256992962

  148. 10000

    Returns: 9901

  149. 91

    Returns: 91

  150. 4

    Returns: 3

  151. 999999

    Returns: 999001

  152. 2

    Returns: 2

  153. 999950884

    Returns: 999919263

  154. 998998998

    Returns: 998970843

  155. 777777777

    Returns: 777768433

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: