Brick Game | HackerEarth Programming Problems and Solution

Brick Game is an easy HackerEarth simulation problem, and it is a good one to practise turn-based thinking. Two people take turns, the amount each one moves grows every round, and you have to report who makes the final move. There is no clever formula needed. What the problem really checks is whether you can model the turns in the right order and stop at exactly the right moment.

Most mistakes here are off-by-one mistakes: checking Motu before Patlu, using < where you needed <=, or forgetting that the last player may place fewer bricks than his full quota. If you get comfortable with this small loop, the same pattern helps you in many "who wins the game" questions in campus coding rounds.

Problem

Patlu and Motu have to shift N bricks from one place to another. To make the job fun, they turn it into a challenge: whoever places the last brick wins. They play in rounds. In round i, Patlu goes first and places i bricks, and then Motu places 2 × i bricks. Round 1 is Patlu 1, Motu 2. Round 2 is Patlu 2, Motu 4, and so on. Your job is to say who places the final brick.

The old statement only says "who puts the last brick", so here is how I read it (and how the sample works): if a player's turn comes and the bricks left are less than or equal to his quota for that turn, he places all of them and he is the one who puts the last brick.

Input: one line with a single integer N, the total number of bricks.

Output: print Patlu if Patlu places the last brick, otherwise print Motu. No quotes.

Constraints: 1 ≤ N ≤ 10000.

Input:
13

Output:
Motu

Approach

Think of it as a counter that goes down. You keep a variable remaining that starts at N, and a round number that starts at 1. Then you simply act out the game.

1. Start round 1.
2. Patlu's turn. He wants to place round bricks. If remaining <= round, he can finish the pile on this turn, so Patlu wins and you stop. Otherwise subtract round from remaining.
3. Motu's turn. He wants to place 2 * round bricks. If remaining <= 2 * round, Motu finishes the pile and wins. Otherwise subtract 2 * round.
4. Move to the next round and repeat.

The order inside a round matters. Patlu always moves first, so you must check him first. If you check Motu first, the answer flips for many inputs.

Why <= and not <? If exactly 3 bricks are left and it is Motu's turn in round 2 (quota 4), he places those 3 and the pile is empty, so he put the last one. If 4 are left and his quota is 4, he places all 4 and again he is the last. Equal counts as "finishes the pile", so the check is <=.

Dry run with N = 13:

• Round 1: Patlu needs 1, 13 left, so he places 1 and 12 remain. Motu needs 2, places 2, 10 remain.
• Round 2: Patlu places 2, 8 remain. Motu places 4, 4 remain.
• Round 3: Patlu's quota is 3, but 4 are left, so he places 3 and 1 remains. Motu's quota is 6 and only 1 brick is left, so Motu places it. Answer: Motu.

The loop runs only a handful of times. Each round removes 3 × round bricks, so after k rounds about 1.5 × k² bricks are gone. For N = 10000 that is under 100 rounds.

Solution in Java

The old solution on this page kept a running total of placed bricks instead of a remaining count. It gives the same answers (I checked every N from 1 to 10000 against it), but counting down is easier to read, so that is what I use below.

import java.util.Scanner;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int remaining = sc.nextInt();   // bricks still left to place

        for (int round = 1; ; round++) {
            // Patlu's turn: he wants to place 'round' bricks
            if (remaining <= round) {
                System.out.println("Patlu");
                break;
            }
            remaining -= round;

            // Motu's turn: he wants to place 2 * round bricks
            if (remaining <= 2 * round) {
                System.out.println("Motu");
                break;
            }
            remaining -= 2 * round;
        }
        sc.close();
    }
}

I ran it on the sample and a few edge cases:

• N = 13 prints Motu (the sample).
• N = 1 prints Patlu. He needs 1 and 1 is left, so he finishes it on the very first move.
• N = 2 prints Motu. Patlu places 1, and Motu places the last 1 even though his quota is 2.
• N = 4 prints Patlu. Round 1 uses 3 bricks, and in round 2 Patlu's quota of 2 covers the 1 brick left.
• N = 10000 prints Patlu.

Output

Motu

Complexity

Time: O(√N). Bricks removed grow roughly with the square of the round number, so the number of rounds grows like the square root of N. For this constraint that is tiny.

Space: O(1). Only a few integer variables.

If you want a constant-time answer you can find the largest full round k with 3 × k(k+1)/2 <= N and then look at what is left. That is a nice exercise, but with N up to 10000 the simulation is simpler and safer in a contest.

Common mistakes

• Checking Motu before Patlu inside a round. Patlu always moves first in every round.
• Using remaining < quota instead of <=. When the bricks left equal the quota, the current player still places the last brick.
• Subtracting first and checking for a negative number afterwards, but then printing the wrong player because the subtraction already moved you past the turn.
• Printing "patlu" or adding quotes. The judge compares text exactly, so match the case shown in the output format.

Another short HackerEarth simulation on the site: Lift queries. You may also like Cost of balloons.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerEarth solutions All coding problems MCQ practice