Problem Statement
A positive integer n is written on a board, and two players take turns making moves.
In each move, the player selects a positive integer m that is a proper substring of the number currently written on the board. The number on the board is then decreased by m. A proper substring is a substring that doesn't equal the whole string.
For example, if a board contains the number 2309, a player can select m = 2, 3, 9, 23, 30, 230 or 309. Thus the possible moves from 2309 are 2000, 2079, 2279, 2286, 2300, 2306 and 2307.
A player who can't make a valid move loses the game.
Return the number m that the first player should select in his first move in order to win the game. If there are several such numbers, return the smallest among them. If the first player cannot win the game, return -1.
Definition
- Class:
- TakeSubstringGame
- Method:
- winningMove
- Parameters:
- int
- Returns:
- int
- Method signature:
- int winningMove(int n)
- (be sure your method is public)
Constraints
- n will be between 1 and 1000000, inclusive.
Examples
5
Returns: -1
A single-digit number doesn't have a proper substring, so there is no valid move for the first player. Thus, the second player wins.
10
Returns: 1
Subtracting 0 is not a valid move (m must be positive). So the only valid move is to subtract 1. Now the second player receives number 9 and can't make a move, providing victory for the first player.
17
Returns: -1
Subtracting 7 will leave the second player with number 10, which is favorable for him, as shown in example above. Therefore the first player should subtract 1 and leave 16. Similarly, the second player will move on to 15. Three more such pairs of moves and the first player will be facing number 11. He will then subtract 1 and lose as shown above. Thus the second player wins.
239
Returns: 9
The optimal first move is to subtract either 9 or 23, leaving 230 or 216. In case of a tie, you should return the smallest subtracted number which is 9.
566
Returns: 66
Subtract 66 and leave your opponent with 500, which is apparently a losing position.
23900
Returns: -1
No first move is advantageous for the first player.
1
Returns: -1
2
Returns: -1
6
Returns: -1
8
Returns: -1
9
Returns: -1
11
Returns: -1
12
Returns: 1
18
Returns: 1
19
Returns: -1
20
Returns: -1
21
Returns: 1
50
Returns: -1
64
Returns: 4
99
Returns: 9
100
Returns: 10
101
Returns: -1
110
Returns: 1
131
Returns: -1
133
Returns: -1
176
Returns: -1
178
Returns: -1
200
Returns: 2
203
Returns: 20
239
Returns: 9
241
Returns: -1
243
Returns: 2
362
Returns: -1
365
Returns: 3
367
Returns: -1
369
Returns: -1
400
Returns: -1
555
Returns: 55
600
Returns: -1
987
Returns: 87
1000
Returns: 100
1098
Returns: -1
1100
Returns: -1
2007
Returns: 2
3316
Returns: -1
3323
Returns: 33
3324
Returns: -1
5660
Returns: 660
9999
Returns: 999
10000
Returns: 1000
10532
Returns: -1
26830
Returns: 68
26832
Returns: 26
26834
Returns: -1
26836
Returns: 2
26838
Returns: -1
60708
Returns: 708
100096
Returns: 9
100098
Returns: -1
100102
Returns: 2
111046
Returns: -1
111048
Returns: -1
142962
Returns: -1
142968
Returns: 6
146238
Returns: 238
147238
Returns: -1
149876
Returns: 6
173737
Returns: -1
183222
Returns: -1
239519
Returns: 519
308443
Returns: -1
341095
Returns: -1
375375
Returns: 375
398765
Returns: 8765
400000
Returns: -1
566239
Returns: 66239
700050
Returns: 50
702000
Returns: 2000
777777
Returns: 77777
800000
Returns: -1
898989
Returns: 98989
900000
Returns: -1
901010
Returns: 1010
987654
Returns: 87654
997755
Returns: 97755
999971
Returns: 99971
999996
Returns: 99996
999999
Returns: 99999
1000000
Returns: 100000
54215
Returns: 4215
979539
Returns: 79539
939959
Returns: 39959
101037
Returns: -1
555555
Returns: 55555
999990
Returns: 99990
100001
Returns: -1