Problem Statement
Devu loves to play games.
This problem is about a game he recently played.
In the game there are n locations, numbered 0 through n-1.
Each location has one entrance and one exit.
You are given a
Devu started the game by entering location 0. Return "Win" (quotes for clarity) if he can win the game. Otherwise, return "Lose". Note that the return value is case-sensitive.
Definition
- Class:
- DevuAndGame
- Method:
- canWin
- Parameters:
- int[]
- Returns:
- String
- Method signature:
- String canWin(int[] nextLevel)
- (be sure your method is public)
Constraints
- nextLevel will have between 1 and 50 elements, inclusive.
- Each element in nextLevel will be either -1 or will be between 0 and n - 1, inclusive.
Examples
{1, -1}
Returns: "Win"
Devu will start in location 0. The exit from this location will bring him to location 1, and when he reaches the exit from location 1 he wins the game.
{1, 0, -1}
Returns: "Lose"
Devu will go back and forth between locations 0 and 1. He is unable to reach the exit from location 2.
{0, 1, 2}
Returns: "Lose"
The exit from location 0 leads back to location 0. Devu is unable to reach the other locations.
{29,33,28,16,-1,11,10,14,6,31,7,35,34,8,15,17,26,12,13,22,1,20,2,21,-1,5,19,9,18,4,25,32,3,30,23,10,27}
Returns: "Win"
There can be multiple x such that nextLevel[x] is -1. In order to win the game, Devu has to reach any single location with this property.
{17,43,20,41,42,15,18,35,-1,31,7,33,23,33,-1,-1,0,33,19,12,42,-1,-1,9,9,-1,39,-1,31,46,-1,20,44,41,-1,-1,12,-1,36,-1,-1,6,47,10,2,4,1,29}
Returns: "Win"
{3, 1, 1, 2, -1, 4}
Returns: "Lose"
In this game, Devu will go from location 0 to location 3, from there to location 2, and from there to location 1. There he will get stuck, as the exit from location 1 leads back to location 1.
{15,10,18,36,32,38,2,4,21,33,12,13,-1,30,44,-1,28,19,25,14,42,22,27,7,3,41,5,46,17,26,40,20,37,34,23,43,11,45,6,16,9,31,35,39,1,29,24}
Returns: "Win"
{27,28,6,11,24,2,41,4,22,5,8,17,9,15,45,18,23,21,-1,37,44,10,14,1,25,32,30,3,31,7,-1,40,38,16,42,43,19,29,33,12,39,20,35,13,46,36,26}
Returns: "Win"
{15,19,16,24,5,8,37,13,40,25,14,29,45,28,30,31,27,3,34,7,36,17,43,38,44,42,-1,21,11,23,2,1,20,22,32,33,39,26,35,4,41,12,10,46,6,9,18}
Returns: "Win"
{14,6,7,5,18,12,31,33,46,44,-1,38,30,36,15,34,29,40,11,4,39,41,3,43,35,10,22,16,45,19,9,37,27,28,17,5,23,26,8,13,2,42,24,21,20,32,25}
Returns: "Win"
{16,38,18,8,24,32,42,45,2,10,30,26,23,-1,15,35,39,46,37,1,33,19,28,44,43,17,5,34,-1,11,40,41,3,13,6,4,7,31,36,21,27,25,29,20,9,14,22}
Returns: "Win"
{30,9,24,10,8,36,4,46,2,-1,1,33,17,28,35,5,25,19,22,34,15,26,12,45,29,43,38,14,37,7,40,18,16,39,3,21,6,42,41,44,23,11,27,-1,31,20,32}
Returns: "Win"
{10,7,22,28,44,25,1,47,24,37,5,8,31,30,18,4,39,34,-1,9,12,46,11,45,20,15,21,36,33,3,29,6,2,17,26,41,43,35,42,14,32,13,16,8,19,38,23,27}
Returns: "Win"
{42,27,38,43,30,22,24,39,33,7,35,7,40,36,46,45,26,2,10,16,29,8,13,37,11,18,12,32,14,19,34,25,28,41,1,23,17,20,9,3,47,-1,31,21,15,4,6,44}
Returns: "Win"
{6,5,8,2,32,16,18,36,21,12,27,35,37,46,20,39,11,9,31,3,29,1,38,4,17,-1,41,40,-1,13,19,47,45,25,22,15,43,7,44,34,42,10,24,30,23,14,33,26}
Returns: "Win"
{28,40,16,35,-1,7,33,20,12,34,11,38,4,31,3,10,44,23,8,21,18,45,43,15,37,27,29,46,39,36,1,19,47,5,14,42,13,6,41,22,32,30,2,9,17,25,-1,26}
Returns: "Win"
{29,3,21,15,28,33,11,4,31,13,27,7,45,-1,35,17,26,6,42,36,44,19,9,38,37,18,12,34,10,16,47,-1,2,8,22,46,39,41,25,40,20,14,5,23,24,32,30,43}
Returns: "Win"
{31,-1,44,16,15,7,21,28,14,23,29,1,3,45,13,26,6,36,35,33,46,32,40,41,11,17,10,4,47,37,34,9,20,24,43,12,25,5,39,18,27,42,22,19,17,38,2,30}
Returns: "Win"
{41,-1,27,37,31,43,46,20,5,47,30,7,34,33,44,2,-1,42,10,11,1,4,23,36,40,39,14,12,6,28,21,19,35,26,24,29,38,15,32,16,18,17,13,9,8,22,25,45}
Returns: "Win"
{17,5,37,-1,38,42,27,2,34,29,43,7,35,6,4,33,11,30,9,1,-1,41,10,16,46,39,15,24,26,28,13,48,18,22,44,3,23,32,40,47,31,8,25,21,14,19,20,12,45}
Returns: "Win"
{16,21,32,11,20,7,19,42,23,34,6,8,18,-1,39,31,35,22,48,14,17,37,15,41,28,44,47,26,33,1,43,30,36,29,4,3,13,46,9,31,25,12,38,45,5,27,10,24,2}
Returns: "Win"
{6,7,30,27,-1,34,40,31,13,12,39,33,20,37,8,1,3,44,19,5,15,14,21,45,2,45,41,23,46,16,28,11,9,24,47,48,17,36,35,29,38,4,43,22,25,32,10,26,18}
Returns: "Win"
{48,7,26,15,36,39,4,13,30,34,43,38,44,2,20,14,11,42,23,45,28,20,37,25,29,3,9,10,8,22,31,5,47,40,12,24,18,27,21,16,17,-1,32,6,35,1,41,19,46}
Returns: "Win"
{36,32,35,18,22,14,39,41,28,24,8,46,33,10,26,23,42,38,6,44,-1,11,31,7,43,45,9,5,17,12,34,19,25,20,29,47,17,30,4,27,3,13,37,1,16,15,2,40,21}
Returns: "Win"
{38,14,27,2,30,16,32,-1,23,17,3,12,28,37,42,1,9,8,35,46,22,48,11,45,18,44,25,41,24,26,43,40,15,19,13,4,33,36,34,5,29,6,-1,31,7,20,10,39,47}
Returns: "Win"
{23,17,37,40,3,9,27,1,12,21,28,48,22,5,8,26,31,-1,39,46,47,11,2,36,42,20,41,38,6,43,7,25,13,16,15,24,33,-1,44,14,45,29,18,35,19,30,32,34,4}
Returns: "Win"
{31,13,45,15,12,21,43,5,11,30,22,32,44,27,8,41,33,25,42,29,10,-1,31,34,1,7,24,39,2,6,20,35,40,9,16,19,4,17,49,14,23,47,46,36,37,26,48,28,38,3}
Returns: "Win"
{39,30,21,44,45,14,4,37,29,24,8,10,18,17,23,2,43,42,47,3,12,1,7,15,6,22,38,13,33,41,34,-1,26,36,46,5,35,28,0,19,27,16,31,9,49,48,20,11,32,40}
Returns: "Win"
{33,25,45,18,42,40,32,34,43,28,11,39,35,8,24,23,20,5,10,44,47,13,1,26,12,7,2,31,46,16,9,14,-1,4,27,19,37,49,6,48,15,29,21,41,-1,38,17,36,22,30}
Returns: "Win"
{21,25,6,8,12,36,9,46,48,11,19,15,17,-1,16,30,20,35,32,24,7,18,38,14,39,28,13,41,4,45,23,43,49,47,31,37,42,5,33,40,1,3,29,-1,26,27,22,44,2,34}
Returns: "Win"
{40,13,14,34,48,27,18,33,49,20,8,35,46,28,22,38,23,44,9,4,3,45,12,37,11,41,17,-1,5,-1,42,30,6,31,36,2,24,25,32,15,29,19,16,39,1,7,26,10,47,43}
Returns: "Win"
{1,25,6,24,37,8,26,19,29,12,30,23,2,46,32,21,44,38,-1,31,47,20,9,16,41,18,11,45,36,43,49,34,10,3,27,42,17,14,48,13,7,39,-1,4,15,5,22,40,35,28}
Returns: "Win"
{10,47,24,43,8,13,23,31,7,-1,16,32,22,39,46,5,45,1,37,25,18,44,48,3,14,2,29,21,20,27,36,35,15,19,17,30,40,12,41,9,26,42,4,38,28,33,49,6,-1,34}
Returns: "Win"
{-1,0,1,1,-1,2}
Returns: "Win"
{-1,20,-1,12,-1,28,-1,2,0,-1,4,15,28,18,17,5,7,24,-1,-1,15,2,25,-1,3,5,-1,-1,17}
Returns: "Win"
{-1,1,-1,-1}
Returns: "Win"
{6,2,19,-1,7,20,30,41,14,40,8,8,41,-1,4,39,5,-1,34,16,42,19,-1,18,-1,2,27,-1,35,12,26,-1,31,30,15,23,-1,9,29,38,28,25,37}
Returns: "Win"
{-1,-1,-1,-1,17,-1,-1,1,-1,-1,-1,16,-1,7,14,-1,19,-1,-1,-1,17,-1,-1}
Returns: "Win"
{-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,-1,-1,28,-1,-1,-1,2,2,-1,19,-1,33,22,-1,4,-1,-1,-1,-1,-1,25,-1}
Returns: "Win"
{-1,-1,-1,8,-1,29,-1,5,4,27,13,-1,-1,16,-1,-1,27,32,0,24,6,-1,-1,3,-1,13,-1,-1,-1,-1,-1,33,19,21}
Returns: "Win"
{20,-1,18,-1,15,-1,2,-1,9,18,21,-1,4,13,23,-1,-1,3,16,-1,10,-1,1,23}
Returns: "Win"
{-1,8,-1,9,5,12,2,-1,5,1,-1,-1,11,-1,5}
Returns: "Win"
{2,5,10,4,9,-1,-1,1,-1,8,4}
Returns: "Win"
{42,31,-1,18,17,3,32,16,25,-1,-1,46,12,32,29,1,37,-1,33,39,41,-1,30,12,27,15,-1,5,17,8,24,7,36,19,40,16,34,28,-1,41,14,11,13,39,20,21,44}
Returns: "Win"
{-1,2,14,8,1,4,12,-1,9,16,13,17,10,17,-1,-1,6,5}
Returns: "Win"
{4,16,9,1,3,8,-1,17,8,-1,16,10,11,11,-1,17,7,13}
Returns: "Lose"
{9,-1,-1,5,-1,11,29,6,25,27,8,15,14,3,21,16,28,13,26,3,31,30,14,26,13,31,-1,12,7,10,24,18}
Returns: "Win"
{-1,-1,8,14,-1,4,13,18,18,7,17,13,5,2,12,6,6,3,10}
Returns: "Win"
{9,0,8,4,2,-1,8,3,5,7}
Returns: "Win"
{17,36,12,-1,49,-1,-1,-1,15,46,2,-1,-1,12,11,-1,2,36,-1,23,-1,-1,19,-1,4,-1,-1,31,-1,37,11,30,-1,-1,-1,17,47,36,17,37,17,-1,-1,40,44,9,44,22,-1,45}
Returns: "Win"
{25,-1,-1,27,-1,-1,-1,41,16,-1,20,-1,24,46,17,40,21,31,-1,-1,48,0,22,-1,22,15,36,-1,-1,30,13,35,14,-1,-1,10,-1,-1,-1,2,29,32,7,-1,-1,19,41,-1,18,34}
Returns: "Win"
{9,3,4,2,1,10,3,8,5,-1,6}
Returns: "Win"
{6,23,14,15,15,-1,4,18,10,31,16,14,21,28,17,9,26,-1,20,1,1,34,7,8,-1,-1,11,29,35,12,33,30,27,27,7,5,17,13}
Returns: "Win"
{-1,-1,-1,45,-1,14,-1,18,-1,-1,18,-1,-1,39,24,-1,16,-1,39,-1,39,0,30,12,12,0,12,-1,-1,45,29,14,-1,35,-1,-1,-1,32,30,1,-1,43,17,44,23,-1,14}
Returns: "Win"
{30,-1,45,32,-1,21,23,13,34,-1,-1,-1,-1,35,-1,44,14,34,-1,16,-1,40,38,-1,-1,46,-1,-1,28,-1,-1,-1,26,14,-1,36,-1,36,-1,-1,43,-1,-1,7,5,-1,-1}
Returns: "Win"
{7,19,33,-1,-1,7,14,43,-1,-1,3,12,-1,0,-1,-1,46,44,17,32,29,-1,42,-1,-1,-1,-1,-1,41,-1,-1,19,44,40,8,41,-1,15,-1,12,-1,3,-1,-1,5,30,7}
Returns: "Win"
{13,22,38,17,23,37,30,6,27,1,34,26,29,7,-1,44,45,9,-1,21,16,5,43,41,31,36,33,3,32,11,35,25,42,10,46,39,19,20,24,15,-1,2,-1,4,8,12,28}
Returns: "Win"
{4,30,43,19,11,23,7,36,-1,22,12,17,27,3,39,13,20,6,41,37,38,31,18,2,46,24,21,34,9,10,16,8,26,4,45,42,14,44,15,29,28,35,1,40,32,24,5}
Returns: "Win"
{13,9,6,2,12,8,41,16,1,40,43,46,33,28,20,39,27,18,15,14,35,25,34,21,18,38,44,30,10,42,29,19,3,7,23,45,5,17,26,3,32,4,31,11,36,22,37}
Returns: "Lose"
{19,24,41,13,46,18,32,29,31,14,20,34,10,8,2,25,5,28,42,22,38,43,23,4,15,27,30,7,37,11,44,16,26,-1,17,12,1,45,9,36,39,21,40,33,3,35,6}
Returns: "Win"
{27,-1,18,-1,-1,-1,-1,14,8,5,10,-1,7,11,27,21,21,-1,-1,-1,11,47,28,31,45,29,-1,6,-1,-1,16,-1,35,6,-1,23,-1,-1,24,20,11,-1,-1,-1,-1,-1,-1,40}
Returns: "Win"
{32,-1,37,5,19,-1,4,8,-1,-1,13,-1,-1,16,17,-1,46,-1,28,-1,46,32,-1,-1,36,11,-1,0,2,-1,43,10,46,-1,0,19,-1,-1,15,-1,42,-1,41,-1,-1,-1,-1,-1}
Returns: "Win"
{14,-1,11,-1,-1,24,-1,45,-1,-1,14,-1,-1,-1,42,4,-1,-1,11,3,-1,27,25,-1,31,32,13,-1,-1,-1,19,-1,36,32,-1,15,42,32,-1,0,-1,-1,2,-1,36,-1,2,-1}
Returns: "Win"
{5,21,33,15,42,27,17,31,43,16,12,13,7,30,40,4,36,8,34,3,46,19,26,-1,6,11,10,45,35,1,29,25,-1,-1,2,41,39,22,18,14,20,9,28,47,39,24,38,37}
Returns: "Win"
{13,21,32,37,12,22,40,-1,6,28,34,36,2,16,35,42,27,45,31,29,47,23,8,20,3,43,25,18,17,38,7,14,10,1,39,11,33,20,24,15,26,9,41,46,5,44,19,4}
Returns: "Lose"
{44,47,16,40,18,9,33,37,41,29,36,19,32,17,24,4,3,25,10,35,5,22,14,42,38,28,31,26,2,8,11,39,30,7,32,2,20,1,12,46,27,43,45,6,21,15,23,13}
Returns: "Lose"
{12,23,15,41,30,43,36,33,26,8,28,4,29,7,45,38,14,25,17,39,16,22,24,9,34,37,10,42,3,13,18,47,20,5,6,1,2,35,46,44,21,27,32,40,-1,31,11,19}
Returns: "Win"
{-1,45,-1,2,18,18,-1,16,-1,22,-1,3,-1,15,-1,-1,6,15,-1,-1,-1,35,-1,33,-1,8,37,-1,42,-1,22,-1,35,-1,-1,-1,-1,2,-1,-1,31,15,-1,-1,-1,-1,-1,-1,39}
Returns: "Win"
{36,-1,-1,17,18,-1,26,-1,-1,10,-1,0,-1,-1,-1,37,35,-1,-1,-1,-1,-1,-1,-1,-1,45,14,26,-1,-1,-1,-1,15,43,-1,-1,12,48,-1,-1,45,-1,9,26,45,4,-1,-1,-1}
Returns: "Win"
{31,35,7,-1,-1,-1,-1,-1,13,-1,-1,-1,11,24,-1,47,-1,17,-1,-1,-1,-1,47,-1,36,-1,-1,38,47,-1,16,32,43,42,26,47,4,33,-1,23,-1,47,46,38,30,-1,32,40,21}
Returns: "Win"
{5,12,-1,35,23,31,33,36,48,13,21,19,25,39,30,4,-1,10,20,38,47,41,28,6,8,3,40,17,34,-1,24,14,26,11,15,9,44,1,27,42,37,22,45,7,38,18,32,43,46}
Returns: "Lose"
{27,30,21,14,31,39,15,5,40,45,8,35,26,34,4,42,12,44,25,24,2,-1,18,19,48,9,37,36,38,-1,46,43,23,11,16,3,17,20,6,33,13,10,7,41,32,1,28,44,22}
Returns: "Win"
{4,21,20,38,35,25,3,5,12,6,43,41,46,22,48,8,42,10,39,18,48,44,15,19,11,40,2,33,32,1,45,31,17,30,9,13,34,29,24,27,37,7,23,16,26,14,47,28,36}
Returns: "Lose"
{42,5,26,18,13,21,25,12,31,19,24,27,17,45,46,23,15,35,39,22,47,36,47,30,37,11,16,2,9,43,7,14,29,1,48,8,10,32,3,34,6,4,33,44,40,28,20,38,41}
Returns: "Lose"
{-1,-1,36,-1,46,-1,25,19,13,15,22,-1,48,-1,-1,-1,-1,-1,9,-1,-1,1,3,22,-1,22,40,15,12,9,-1,-1,-1,-1,-1,30,-1,8,31,46,-1,28,-1,-1,17,12,-1,33,1,30}
Returns: "Win"
{41,42,11,-1,-1,-1,-1,29,-1,-1,14,-1,16,19,-1,-1,-1,-1,29,1,-1,36,-1,-1,17,21,-1,4,31,-1,-1,32,10,21,-1,-1,-1,47,19,-1,3,8,-1,-1,-1,-1,20,-1,-1,49}
Returns: "Win"
{23,-1,-1,-1,8,32,-1,32,36,-1,-1,3,-1,18,10,45,-1,-1,-1,12,13,-1,-1,9,-1,2,22,-1,14,-1,28,-1,7,23,-1,48,42,-1,31,-1,-1,-1,-1,5,15,-1,12,29,-1,-1}
Returns: "Win"
{29,6,36,15,41,18,22,20,1,11,-1,39,7,26,45,25,40,35,24,44,23,48,-1,34,13,12,46,-1,48,17,3,30,38,5,4,42,31,14,47,21,33,43,37,19,8,32,49,16,2,9}
Returns: "Win"
{24,11,36,-1,6,26,43,38,21,2,8,39,15,-1,17,3,18,47,35,45,30,25,1,7,37,32,46,48,41,10,4,12,42,28,40,20,14,5,44,7,27,29,49,34,31,16,9,33,22,19}
Returns: "Win"
{19,28,21,17,34,23,36,25,38,45,40,24,13,6,42,35,27,14,26,20,11,8,48,39,3,32,10,33,7,30,41,16,9,49,22,4,31,-1,5,24,47,1,15,18,29,46,2,44,12,43}
Returns: "Lose"
{33,47,27,42,22,28,10,34,25,26,48,5,40,38,16,37,23,3,24,32,15,36,46,19,11,14,45,39,35,8,29,4,43,2,-1,44,13,7,41,49,18,31,21,17,20,1,12,6,30,9}
Returns: "Win"
{35,-1,-1,12,-1,39,33,-1,-1,28,-1,-1,-1,25,-1,-1,40,40,-1,29,-1,-1,-1,13,38,-1,-1,8,-1,-1,-1,3,6,16,-1,32,17,6,-1,32,31,35,26}
Returns: "Win"
{13,-1,2,-1,9,14,1,-1,14,10,3,-1,20,8,4,15,-1,15,-1,-1,-1}
Returns: "Win"
{23,26,-1,16,13,17,12,24,-1,6,11,7,4,14,-1,-1,21,22,3,11,9,5,20,11,27,0,21,18}
Returns: "Win"
{4,-1,36,18,10,-1,-1,-1,-1,-1,33,17,-1,-1,3,-1,-1,2,6,-1,-1,22,-1,24,30,25,9,1,-1,-1,13,-1,7,7,20,9,22}
Returns: "Win"
{19,-1,36,10,37,27,18,43,20,4,41,23,17,9,0,-1,13,22,33,34,24,28,39,6,8,5,21,7,25,-1,35,43,11,30,3,17,38,24,32,16,26,40,2,42}
Returns: "Lose"
{1,0}
Returns: "Lose"
{3,-1,-1,2,7,-1,6,0,4,-1}
Returns: "Win"
{2,0,5,4,-1,3}
Returns: "Win"
{17,18,10,9,6,-1,5,2,14,7,-1,0,14,6,1,-1,-1,12,3}
Returns: "Win"
{1,9,2,-1,-1,3,-1,3,-1,3}
Returns: "Win"
{8,7,6,4,5,0,3,10,10,1,1}
Returns: "Lose"
{8,5,-1,8,4,14,9,14,9,14,-1,11,16,-1,9,13,6}
Returns: "Lose"
{8,12,18,0,8,4,2,13,9,13,11,3,11,18,2,0,18,2,0}
Returns: "Lose"
{27,13,2,35,24,12,-1,7,13,38,32,17,11,-1,36,37,24,7,35,20,36,18,10,33,3,3,1,39,12,5,1,21,20,21,3,11,25,20,1,21}
Returns: "Lose"
{5,1,39,18,5,22,3,21,21,44,19,2,21,41,30,5,0,12,8,15,45,29,41,22,43,27,41,17,21,38,23,4,45,31,31,9,14,25,2,14,19,11,32,33,15,14}
Returns: "Lose"
{32,16,33,21,19,29,31,13,15,16,25,27,31,22,28,23,10,6,28,15,28,23,25,19,30,6,20,35,30,18,-1,20,1,19,13,27}
Returns: "Win"
{-1,0,-1,3,-1}
Returns: "Win"
{1,15,1,-1,10,14,3,10,7,14,10,4,14,11,3,19,16,18,19,19,16,15}
Returns: "Lose"
{3,4,1,2,4,5}
Returns: "Lose"
{39,9,37,36,4,17,32,12,15,23,35,6,10,0,2,32,35,36,1,37,6,30,13,37,22,25,34,29,0,30,4,37,22,27,2,35,4,-1,39,38}
Returns: "Lose"
{-1}
Returns: "Win"
{0}
Returns: "Lose"
{0, 1, 2 }
Returns: "Lose"
{-1 }
Returns: "Win"
{1, 2, 3, -1 }
Returns: "Win"
{2, -1, 0 }
Returns: "Lose"
{2, 2, -1 }
Returns: "Win"
{17, 43, 20, 41, 42, 15, 18, 35, -1, 31, 7, 33, 23, 33, -1, -1, 0, 33, 19, 12, 42, -1, -1, 9, 9, -1, 39, -1, 31, 46, -1, 20, 44, 41, -1, -1, 12, -1, 36, -1, -1, 6, 47, 10, 2, 4, 1, 29 }
Returns: "Win"