You are playing a game with a jar full of candies against an opponent. At each step both you and your opponent can take between one and three candies out of the jar. Whoever makes the last move wins. Given numberOfCandies, print YES if you are sure you can win and NO otherwise.
Example
Input:
let numberOfCandies = 4Expected value/output:
NO
[collapse]
Hint
What are the winning and losing states of the problem?
- 0 candies is a losing state, whoever ends up there can’t win the game.
- 1, 2 and 3 candies are winning states, the player can simply take all the available candies.
- 4 candies is a losing state again because no matter if we pick 1, 2 or 3 candies, the other player will always be able to pick all the remaining ones.
- 5 candies is a winning state because we can pick one candy, and the other player gets into a losing state.
Can you see the rule now?
[collapse]
Solution
let numberOfCandies = 4
func candyJar(numberOfCandies:Int, moves:Int) -> String {
var wins = [Bool](repeatElement(false, count:numberOfCandies+1))
wins[0] = false
for i in 1...numberOfCandies {
for j in 1...moves {
if wins[max(0,i-j)] == false {
wins[i] = true
}
}
}
if wins[numberOfCandies] == true {
return "YES"
}
else {
return "NO"
}
}
print(candyJar(numberOfCandies: numberOfCandies, moves: 3))[collapse]
