We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home
  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Interview Preparation Kits
  3. 1 Week Preparation Kit
  4. Day 3
  5. Tower Breakers

Tower Breakers

Problem
Submissions
Leaderboard
Discussions
Editorial

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 towers.
  • Each tower is of height .
  • The players move in alternating turns.
  • In each turn, a player can choose a tower of height and reduce its height to , where and evenly divides .
  • If the current player is unable to make a move, they lose the game.

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

Example.

There are towers, each units tall. Player has a choice of two moves:
- remove pieces from a tower to leave as
- remove pieces to leave

Let Player remove . Now the towers are and units tall.

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

Now Player has only one move.

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

Player has no move and loses. Return .

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

Returns

  • 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 .

Constraints

Sample Input

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

Sample Output

2
1

Explanation

We'll refer to player as and player as

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

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

Author

forthright48

Difficulty

Easy

Max Score

100

Submitted By

101559

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website