Tower Breakers HackerRank Solution

PROBLEM STATEMENT

Two players are playing a game of Tower Breakers! Player 1 always moves first, and both players always play optimally. The rules of the game are as follows:

1. Initially, there are N towers.
2. Each tower is of height M.
3. The players move in alternating turns.
4. In each turn, a player can choose a tower of height X and reduce its height to Y, where 1 <= Y < X and Y evenly divide X.

If the current player is unable to make a move, they lose the game.

Given the values of N and M, determine which player will win. If the first player wins, return 1. Otherwise, return 2.

How to play Tower Breaker Game

Reduce the size of tower such that height of the tower is divisible by current height.

Every tower can be reduce to size of 1.

If the height tower become 1 , you cannot reduce it more.

Special Case

If there is only one tower , Player 1 always win. As there will be no options for Player 2.

If the height of tower is 1 , Player 2 always win. As there will be no option for Player 1.

Even Towers

Lets take a example , we have two towers of height 4.

case 1:

player1 make the first tower to height 2.

player 2 make the second tower to height 2.

player1 make the first tower to height 1.

player 2 make the second tower to height 1.

Now, player 1 cannot reduce more , so Player 2 wins.

case 2:

player1 make the first tower to height 1.

player 2 make the second tower to height 1.

Now, player 1 cannot reduce more , so Player 2 wins.

Odd Towers

Lets take the example of 3 towers of height 3.

case 1:

player1 make the first tower to height 1.

player 2 make the second tower to height 1.

player1 make the third tower to height 1.

Now, player 2 cannot reduce more , so Player 1 wins.

def towerBreakers(n, m):
    # Write your code here
    if m== 1 or n%2 ==0:
        return 2
    else:
        return 1