[HackerRank - Java] Day 3 - 2. Tower Breakers

2023. 1. 28. 02:42Java/coding test


Tower Breakers

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

  • Initially there are nn towers.
  • Each tower is of height mm.
  • The players move in alternating turns.
  • In each turn, a player can choose a tower of height xx and reduce its height to yy, where 1<=y<x1<= y < x and evenly yy divides xx.
  • 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 . Otherwise, return .

There are 2 towers, each 6 units tall. Player 1 has a choice of two moves:

  • remove 3 pieces from a tower to leave 3 as 6 modulo 3 = 0
  • remove 5 pieces to leave 1

Let Player 1 remove 3. Now the towers are 3 and 6 units tall.

Player 2 matches the move. Now the towers are both 3 units tall.

Now Player 1 has only one move.

Player 1 removes 2 pieces leaving 1. Towers are 1 and 2 units tall.
Player 2 matches again. Towers are both 1 unit tall.

Player 1 has no move and loses. Return 2.

Function Description

Complete the towerBreakers function in the editor below.

towerBreakers has the following paramter(s):

  • int n: the number of towers
  • int m: the height of each tower


  • int: the winner of the game

Input Format

The first line contains a single integer , the number of test cases.
Each of the next lines describes a test case in the form of space-separated integers, and .


  • 1<=t<=1001 <= t <= 100
  • 1<=n,m<=1061 <= n, m <= 10^6

Sample Input

STDIN   Function
-----   --------
2       t = 2
2 2     n = 2, m = 2
1 4     n = 1, m = 4

Sample Output


We'll refer to player 1 as P1P1 and player 2 as P2P2

In the first test case, P1P1 chooses one of the two towers and reduces it to 1. Then P2P2 reduces the remaining tower to a height of 1. As both towers now have height 1, P1P1 cannot make a move so P2P2 is the winner.

In the second test case, there is only one tower of height 4. P1P1 can reduce it to a height of either 1 or 2. P1P1 chooses 1 as both players always choose optimally. Because P2P2 has no possible move, P1P1 wins.

두 플레이어가 타워 브레이커 게임을 하고 있다.(각 플레이어를 P1, P2라고 부르도록 하겠습니다.)
P1은 항상 먼저 움직이며, 두 플레이어는 항상 최적의 방식으로 움직인다.

최초에 n개의 타워가 있고
각 타워의 높이는 m
플레이어들은 번갈아가면서 움직이고
각 턴에서 플레이어는 높이가 x인 타워를 선택할 수 있고, 높이를 y로 줄일 수 있습니다.
(1 <= y < x 이면서, x % y = 0)
플레이어가 움직일 수 없다면 게임에서 진것입니다.

P1이 이기면 1, P2가 이기면 2를 리턴하세요.


설명은 매우 거창한데, 사실 문제는 매우 간단하다.
언제나 P1과 P2는 최적의 방식으로 움직인다는 것이고

y로 줄일 수 있으면서 x를 y로 나눴을 때 나머지가 0이면 된다는 말인데.
이는 즉, 높이가 12든 6이든 1로 나눠 떨어지기 때문에 1로 줄일 수 있다는 의미가 된다.

최초에 타워 높이가 2보다 작을 경우 첫 타자인 P1이 움직일 수 없기 때문에 P2가 이기고
그 외의 경우, 타워 수가 홀수면 P1이 이기고 짝수면 P2가 이긴다.

public static int towerBreakers(int n, int m) {
    return m < 2 || n % 2 == 0 ? 2 : 1;