HackerRank Tower Breakers Java Solution Explained
Problem Overview
Original Problem: Tower Breakers | HackerRank
Difficulty: Easy
Category: Game Theory, Math
Description: In a two-player game with some number of equal-height towers, players take turns reducing the height of a tower. Player 1 moves first, and both players play optimally. The player who cannot make a move loses. Determine the winner: return 1 if Player 1 wins, or 2 if Player 2 wins.
This problem, part of HackerRank’s One Week Preparation Kit, introduces beginners to game theory and logical reasoning in Java, key skills for coding interviews.
Understanding the Problem
The Tower Breakers problem involves a game where two players alternate turns, reducing the height of one of n towers. Each tower starts with height m, and a valid move reduces a tower’s height from x to y, where y is a divisor of x and less than x. If a player cannot make a move (all towers are height 1), they lose. Given n and m, we need to determine which player wins if both play optimally. For example, with n = 2, m = 2, Player 1 can reduce one tower to 1, leaving Player 2 with no moves on that tower but a move on the other, leading to a strategic analysis of who wins. The goal is to return 1 (Player 1 wins) or 2 (Player 2 wins).
Input and Output
Input:
First line: An integer t, the number of test cases.
For each test case: Two space-separated integers n (number of towers) and m (height of each tower).
Output:
For each test case, an integer: 1 if Player 1 wins, or 2 if Player 2 wins.
Constraints:
1 ≤ t ≤ 100
1 ≤ n, m ≤ 10^6
Initial Reasoning
To determine the winner, we need to analyze the game’s rules and optimal play:
A player can reduce a tower’s height to any of its divisors (except itself), and the smallest possible height is 1.
If all towers reach height 1, no further moves are possible, and the current player loses.
Since both players play optimally, we need to identify patterns in the outcomes based on n and m.
Key cases to consider:
If m = 1, all towers are height 1, so no moves are possible, and Player 1 loses immediately.
For m > 1, players can always make a move unless all towers are height 1.
The number of towers (n) affects whether Player 1 can force a winning position.
This suggests a game theory approach, where we derive a pattern for the winner based on n and m.
Thought Process
Let’s break down the logic step-by-step:
Game Rules Recap:
Each move reduces a tower’s height to a proper divisor (e.g., a tower of height 6 can be reduced to 1, 2, or 3).
The game ends when no moves are possible (all towers are height 1), and the current player loses.
Players alternate, with Player 1 starting.
Analyze Key Cases:
Case 1: m = 1
All towers are height 1, so Player 1 cannot move and loses immediately. Return 2 (Player 2 wins).
Case 2: n is even, m > 1
Suppose n = 2, m = 2. Player 1 reduces one tower to 1. Player 2 reduces the other to 1. No moves remain, so Player 1 loses.
For even n, Player 2 can mirror Player 1’s moves, reducing each tower to 1 in pairs, forcing Player 1 to face a no-move state.
Thus, Player 2 wins when n is even and m > 1.
Case 3: n is odd, m > 1
Suppose n = 1, m = 2. Player 1 reduces the tower to 1, and Player 2 cannot move, so Player 1 wins.
For odd n, Player 1 can reduce towers strategically (e.g., to height 1), leaving Player 2 with no winning moves.
Thus, Player 1 wins when n is odd and m > 1.
Derive the Pattern:
If m = 1, Player 1 cannot move, so Player 2 wins (return 2).
If m > 1 and n is even, Player 2 wins by mirroring moves (return 2).
If m > 1 and n is odd, Player 1 wins by forcing a losing state for Player 2 (return 1).
This can be simplified: Player 1 wins if n is odd and m > 1; otherwise, Player 2 wins.
Handle Constraints:
n, m ≤ 10^6, but the solution depends only on n’s parity and whether m = 1, so no complex calculations are needed.
Multiple test cases (t ≤ 100) are handled independently.
Use int for n and m, as they fit within 32-bit integers.
Edge Cases:
If n = 1, m = 1: Player 1 cannot move, so Player 2 wins.
If n = 1, m > 1: Player 1 reduces the tower to 1, and Player 2 loses.
If m > 1, the parity of n determines the outcome.
This approach is optimal with O(1) time complexity per test case and O(1) space, making it efficient and beginner-friendly.
Pseudocode
// towerBreakers method:
If the height of the towers is 1 or the number of towers are even
Return 2
Else
Return 1
Solution Code
// Note: This is one of many possible solutions
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public static int towerBreakers(int n, int m) {
// If m=1 (no moves possible) or n is even (Player 2 can mirror moves), Player 2 wins, otherwise Player 1 wins
return (m == 1 || n % 2 == 0) ? 2 : 1;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, t).forEach(tItr -> {
try {
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);
int result = Result.towerBreakers(n, m);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}Step-by-Step Explanation
Let’s break down the Java solution for beginners:
Input Handling:
The main method reads:
t, the number of test cases, using Integer.parseInt(bufferedReader.readLine().trim()).
For each test case: Two space-separated integers n and m from a single line, parsed using split and Integer.parseInt.
Determine the Winner:
In towerBreakers, use a single condition to decide the winner:
Check if m == 1 (no moves possible) or n % 2 == 0 (n is even, Player 2 can mirror moves).
If either is true, return 2 (Player 2 wins).
Otherwise, return 1 (Player 1 wins, as n is odd and m > 1).
The ternary operator (m == 1 || n % 2 == 0) ? 2 : 1 concisely encodes this logic.
Output Handling:
For each test case, write the result (1 or 2) to the output file using bufferedWriter.write(String.valueOf(result)).
Add a newline with bufferedWriter.newLine().
Close bufferedReader and bufferedWriter to prevent resource leaks.
Common Mistakes to Avoid
Here are common pitfalls for beginners:
Simulating the Game: Trying to simulate each move (e.g., reducing tower heights) is unnecessary and inefficient for large n, m (up to 10^6). The pattern-based approach is simpler.
Misinterpreting Rules: Assuming invalid moves (e.g., y not dividing x) or missing the optimal play requirement can lead to incorrect logic. Always assume optimal moves.
Ignoring Edge Cases: Forgetting that m = 1 means no moves are possible can result in wrong outputs. Check m = 1 explicitly.
Real-World Application
The Tower Breakers problem introduces game theory, which is used in competitive programming, AI, and strategy games. For example, in AI-driven game design, similar logic determines optimal moves in turn-based games. In economics, game theory models strategic interactions between agents. This problem teaches pattern recognition and logical deduction, skills valuable in algorithm design and problem-solving.
FAQs
Q: Why does Player 2 win when n is even?
A: With an even number of towers and m > 1, Player 2 can mirror Player 1’s moves, reducing towers in pairs until none remain, forcing Player 1 to lose.
Q: Why is m = 1 a special case?
A: If m = 1, all towers are height 1, so no moves are possible. Player 1, moving first, loses immediately, so Player 2 wins.
Q: Can we solve this by simulating moves?
A: Simulation is possible for small cases but inefficient for n, m up to 10^6. The pattern-based approach (checking n’s parity and m) is faster and sufficient.