Problem Statement
N cells are located around a circle. Cells are numbered 1 through N in the clockwise direction.
Initially, you can place a token into any one of these cells.
In each turn, you look at the number of the cell containing the token and you calculate s, the sum of the digits in that number. You then move the token s cells clockwise.
This process continues until you move the token into a cell that already contained the token before. Your score is the number of cells that were visited by the token at least once during the process (including the initial cell).
Given N, return the maximal possible score you can get.
Definition
- Class:
- RoundAboutCircle
- Method:
- maxScore
- Parameters:
- int
- Returns:
- int
- Method signature:
- int maxScore(int N)
- (be sure your method is public)
Constraints
- N will be between 1 and 200000, inclusive.
Examples
4
Returns: 3
The list of possible moves looks like this: 1->2 2->4 3->2 4->4 You can only visit 3 out of 4 cells, and there are two ways to do so: 1->2->4->4 and 3->2->4->4.
5
Returns: 4
If you start on cell 5, the process will terminate after the first move. Otherwise, the token will travel along the loop 1->2->4->3->1 until the entire loop is visited, thus making your score equal to 4.
17
Returns: 11
The longest path of the token is 5->10->11->13->17->8->16->6->12->15->4->8.
566
Returns: 176
1
Returns: 1
200000
Returns: 18707
99974
Returns: 14885
199999
Returns: 27604
2
Returns: 2
3
Returns: 2
6
Returns: 3
12
Returns: 7
30
Returns: 15
42
Returns: 17
918
Returns: 134
2412
Returns: 263
5517
Returns: 460
13788
Returns: 1149
21177
Returns: 1583
29052
Returns: 2000
52497
Returns: 3206
80100
Returns: 4548
94302
Returns: 5118
100037
Returns: 14868
148518
Returns: 8052
176706
Returns: 9228
192636
Returns: 9834
198162
Returns: 10026
199350
Returns: 10062
199926
Returns: 10080
199971
Returns: 10086
199998
Returns: 10080
128
Returns: 67
218
Returns: 120
563
Returns: 247
836
Returns: 281
1900
Returns: 494
3001
Returns: 759
4583
Returns: 1021
9515
Returns: 2070
19606
Returns: 3802
32768
Returns: 5690
40054
Returns: 6677
55651
Returns: 9363
65270
Returns: 10574
95851
Returns: 14338
101027
Returns: 15157
125999
Returns: 18637
154651
Returns: 22817
185225
Returns: 26549
196058
Returns: 27392
198616
Returns: 27784
199912
Returns: 27940
199946
Returns: 27942
199952
Returns: 27946
198765
Returns: 10044
192342
Returns: 17865
199997
Returns: 18966
199943
Returns: 27909
199000
Returns: 27489
187549
Returns: 26156
189999
Returns: 9720
123533
Returns: 18035
46573
Returns: 5176
199995
Returns: 18417