Candy Jar

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 = 4

Expected 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]
1 Star2 Stars3 Stars4 Stars5 Stars (14 votes, average: 1.43 out of 5)
Loading...
Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)