Statistics

Problem Statement for "KidsGame"

Problem Statement

Little Johnny and his friends play a lot of games in which each player gets a different role. The roles are assigned using a method reminiscent of "eenie meenie miny moe" rhymes. n kids stand in a circle and are numbered from 1 to n going in a clockwise direction. They choose a number m, and starting with kid 1, they go around the circle in a clockwise direction, counting off from 1 to m. The kid who gets number m is eliminated from the circle, and the counting starts again at 1 with the next kid. The ith eliminated kid gets the ith role in the game. Johnny wants to know what role he will get if he is kid number k in the circle.

For example, consider the case where n = 5, m = 2, and k = 3. The kids are arranged clockwise as follows: 1, 2, 3, 4, 5. Starting with kid 1, they start counting from 1 to 2. Kid 2 gets number 2, so he is eliminated from the circle, which now looks like: 1, 3, 4, 5. They start counting again with kid 3. Kid 4 gets number 2 this time, so he is the next to get eliminated. Then, kid 1 is eliminated, followed by kid 5, and finally, kid 3. Johnny is kid 3, so he is the 5th kid to get eliminated, and he is assigned the 5th role.

Given n, m, and k, return the role assigned to Johnny. Roles are 1-indexed, so the 1st eliminated kid gets role 1, the 2nd eliminated kid gets role 2, and so on.

Definition

Class:
KidsGame
Method:
kthKid
Parameters:
int, int, int
Returns:
int
Method signature:
int kthKid(int n, int m, int k)
(be sure your method is public)

Constraints

  • n and m will be between 1 and 500000, inclusive.
  • k will be between 1 and n, inclusive.

Examples

  1. 10

    3

    6

    Returns: 2

  2. 10

    3

    4

    Returns: 10

  3. 1000

    3000

    7

    Returns: 530

  4. 500000

    250000

    93986

    Returns: 358332

  5. 5

    2

    3

    Returns: 5

    This is the example previously explained.

  6. 1

    10

    1

    Returns: 1

    There is only one kid, so he will be eliminated on the first step.

  7. 99

    100

    99

    Returns: 94

  8. 19999

    7

    5

    Returns: 18019

  9. 99999

    11111

    3

    Returns: 69557

  10. 500000

    499999

    322414

    Returns: 95635

  11. 11

    3

    7

    Returns: 11

  12. 11

    7

    4

    Returns: 10

  13. 11

    11

    4

    Returns: 10

  14. 11

    15

    10

    Returns: 11

  15. 11

    19

    4

    Returns: 10

  16. 11

    23

    3

    Returns: 9

  17. 11

    27

    6

    Returns: 8

  18. 11

    31

    11

    Returns: 11

  19. 11

    35

    10

    Returns: 10

  20. 11

    39

    10

    Returns: 10

  21. 13

    3

    10

    Returns: 9

  22. 13

    7

    3

    Returns: 9

  23. 13

    11

    6

    Returns: 9

  24. 13

    15

    12

    Returns: 9

  25. 13

    19

    2

    Returns: 11

  26. 13

    23

    11

    Returns: 9

  27. 13

    27

    7

    Returns: 11

  28. 13

    31

    8

    Returns: 12

  29. 13

    35

    8

    Returns: 13

  30. 13

    39

    10

    Returns: 11

  31. 15

    3

    10

    Returns: 10

  32. 15

    7

    4

    Returns: 14

  33. 15

    11

    14

    Returns: 11

  34. 15

    15

    7

    Returns: 12

  35. 15

    19

    11

    Returns: 13

  36. 15

    23

    14

    Returns: 11

  37. 15

    27

    8

    Returns: 14

  38. 15

    31

    11

    Returns: 11

  39. 15

    35

    10

    Returns: 10

  40. 15

    39

    3

    Returns: 12

  41. 17

    3

    16

    Returns: 12

  42. 17

    7

    15

    Returns: 15

  43. 17

    11

    14

    Returns: 16

  44. 17

    15

    11

    Returns: 12

  45. 17

    19

    1

    Returns: 16

  46. 17

    23

    11

    Returns: 13

  47. 17

    27

    11

    Returns: 14

  48. 17

    31

    3

    Returns: 15

  49. 17

    35

    17

    Returns: 15

  50. 17

    39

    15

    Returns: 14

  51. 19

    3

    4

    Returns: 14

  52. 19

    7

    5

    Returns: 14

  53. 19

    11

    7

    Returns: 13

  54. 19

    15

    18

    Returns: 13

  55. 19

    19

    18

    Returns: 15

  56. 19

    23

    8

    Returns: 14

  57. 19

    27

    12

    Returns: 18

  58. 19

    31

    18

    Returns: 19

  59. 19

    35

    2

    Returns: 18

  60. 19

    39

    5

    Returns: 18

  61. 2

    2

    1

    Returns: 2

  62. 61355

    81783

    5665

    Returns: 45940

  63. 98295

    63339

    57647

    Returns: 94551

  64. 82168

    86940

    1719

    Returns: 80093

  65. 51756

    64056

    2884

    Returns: 36994

  66. 69280

    57661

    7361

    Returns: 57491

  67. 54705

    85616

    23037

    Returns: 43481

  68. 75842

    58856

    64098

    Returns: 63630

  69. 91767

    63707

    83980

    Returns: 84314

  70. 500000

    500000

    2

    Returns: 362658

  71. 500000

    500000

    74191

    Returns: 475701

  72. 500000

    500000

    74192

    Returns: 127809

  73. 255643

    469280

    11269

    Returns: 234355

  74. 454705

    485616

    147385

    Returns: 436576

  75. 446084

    400647

    370348

    Returns: 436625

  76. 453454

    337230

    416029

    Returns: 419376

  77. 334846

    291126

    145218

    Returns: 302662

  78. 381406

    338883

    138442

    Returns: 362447

  79. 377030

    317786

    47086

    Returns: 367718

  80. 291764

    493885

    102162

    Returns: 284447

  81. 310315

    290668

    224

    Returns: 304687

  82. 500000

    1

    500000

    Returns: 500000

  83. 500000

    500000

    50000

    Returns: 75608

  84. 500000

    250000

    99999

    Returns: 266841

  85. 500000

    499999

    1

    Returns: 476477

  86. 500000

    500000

    250000

    Returns: 290278

  87. 500000

    400000

    177

    Returns: 116239

  88. 500000

    500000

    500000

    Returns: 1

  89. 99999

    11111

    3

    Returns: 69557

  90. 500000

    11111

    3

    Returns: 328693

  91. 500000

    500000

    300000

    Returns: 138262

  92. 500000

    11111

    7

    Returns: 492900

  93. 500000

    500000

    4564

    Returns: 460688

  94. 500000

    2

    499999

    Returns: 375000

  95. 500000

    100000

    43

    Returns: 441344

  96. 500000

    500000

    14555

    Returns: 124402

  97. 500000

    500000

    499999

    Returns: 120281

  98. 500000

    1

    500000

    Returns: 500000

  99. 500000

    25000

    499999

    Returns: 88716

  100. 500000

    493222

    52

    Returns: 361568

  101. 500000

    500000

    74176

    Returns: 500000

  102. 500000

    8

    3

    Returns: 243546

  103. 99999

    11117

    3

    Returns: 44163

  104. 500000

    8

    4

    Returns: 117188

  105. 5

    2

    1

    Returns: 3

  106. 499999

    475895

    135867

    Returns: 7626

  107. 499999

    1

    499998

    Returns: 499998

  108. 500000

    499999

    499997

    Returns: 378356

  109. 499999

    11111

    3

    Returns: 398470

  110. 500000

    232991

    66086

    Returns: 90000

  111. 500000

    500000

    2

    Returns: 362658

  112. 500000

    499999

    223118

    Returns: 500000

  113. 50000

    200

    200

    Returns: 1

  114. 500000

    499999

    3

    Returns: 378845

  115. 5

    6

    2

    Returns: 3

  116. 1

    1

    1

    Returns: 1

  117. 444444

    11111

    3

    Returns: 375626

  118. 500000

    499876

    500

    Returns: 494639

  119. 500000

    499000

    3

    Returns: 331423

  120. 500000

    500000

    400000

    Returns: 274559

  121. 500000

    11

    499999

    Returns: 401078

  122. 500000

    500000

    13504

    Returns: 499655

  123. 500000

    400000

    250000

    Returns: 38304

  124. 500000

    500000

    299797

    Returns: 496085

  125. 500000

    250000

    333333

    Returns: 368574

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: