Problem Statement
Shiny wants to give an award to one of the employees in her company. However, all her employees are doing perfect work, so it's hard to pick the one that gets the award. Therefore Shiny organized a game they will play to determine the winner.
At the beginning of the game, all N employees form a circle. Then, they receive t-shirts with numbers 1 through N in clockwise order along the circle. These numbers are never used in the game, we will just use them to identify the winner.
The game is played in turns. The turns are numbered starting from 1. In each turn, Shiny starts by standing in front of some employee (as specified below) and saying "one". Then she moves clockwise along the circle to the next employee and says "two". And so on, until the number she says reaches the threshold for that particular turn. The threshold for turn number t is t^3. (That is, the threshold is 1 for turn 1, 8 for turn 2, 27 for turn 3, and so on.)
At the end of each turn, the employee currently standing in front of Shiny (i.e., the one that received the number t^3) is eliminated. In the very first round Shiny starts in front of the employee with the number 1 on their t-shirt. In each of the following rounds, Shiny starts in front of the next employee clockwise from the one who just got eliminated.
When there is only one employee left in the game, the game ends and the employee wins the award.
You are given the
Definition
- Class:
- ChooseTheBestOne
- Method:
- countNumber
- Parameters:
- int
- Returns:
- int
- Method signature:
- int countNumber(int N)
- (be sure your method is public)
Constraints
- N will between 1 and 5000, inclusive.
Examples
3
Returns: 2
In the first round, Shiny stands in front of employee 1, says "one" and eliminates him. In the second round, Shiny starts in front of employee 2. She says "one" to employee 2, "two" to employee 3, "three" to employee 2 again, ..., and "eight" to employee 3. Thus, employee 3 gets eliminated and employee 2 wins the award.
6
Returns: 6
10
Returns: 8
1234
Returns: 341
2414
Returns: 1368
1506
Returns: 767
1113
Returns: 405
2462
Returns: 1286
3423
Returns: 1635
3647
Returns: 1386
2172
Returns: 833
2065
Returns: 1520
2749
Returns: 299
1756
Returns: 732
2471
Returns: 583
1840
Returns: 551
2577
Returns: 42
2293
Returns: 1389
2201
Returns: 1070
1839
Returns: 1618
120
Returns: 32
3522
Returns: 818
2078
Returns: 1283
657
Returns: 208
1421
Returns: 634
2040
Returns: 276
1660
Returns: 776
1366
Returns: 499
201
Returns: 117
4887
Returns: 2687
1780
Returns: 654
2056
Returns: 87
1090
Returns: 158
996
Returns: 706
612
Returns: 72
1298
Returns: 806
1650
Returns: 1526
1634
Returns: 1108
2899
Returns: 2654
2306
Returns: 250
1369
Returns: 997
1261
Returns: 482
3396
Returns: 615
2793
Returns: 1289
2566
Returns: 1583
2856
Returns: 2210
3607
Returns: 2681
1080
Returns: 380
2626
Returns: 112
4207
Returns: 923
2852
Returns: 2549
2525
Returns: 2112
2349
Returns: 587
3063
Returns: 2587
3306
Returns: 2580
1902
Returns: 1770
2141
Returns: 1195
2637
Returns: 2533
559
Returns: 189
3037
Returns: 228
3588
Returns: 3478
4916
Returns: 1508
4888
Returns: 2755
1781
Returns: 1471
929
Returns: 662
867
Returns: 813
2643
Returns: 1740
1028
Returns: 482
498
Returns: 112
62
Returns: 17
1235
Returns: 606
386
Returns: 89
3801
Returns: 835
611
Returns: 482
3748
Returns: 1886
1433
Returns: 733
612
Returns: 72
56
Returns: 20
2280
Returns: 1986
101
Returns: 12
3834
Returns: 2837
4884
Returns: 40
4338
Returns: 45
2205
Returns: 900
1
Returns: 1
2
Returns: 2
5000
Returns: 4200
4999
Returns: 1656
4000
Returns: 1680
842
Returns: 140
1765
Returns: 45
4894
Returns: 2035