LeetCode Problems with One Line Solution

Below are three interesting "brain teaser" problems I summarized while practicing coding. These problems can be solved using algorithmic programming, but with a bit of thought, you can find patterns and come up with the answers directly.

One, Nim Game

LeetCode problem 292 "Nim Game" presents the following game rules:

You and your friend are in front of a pile of stones. You take turns picking stones, with a minimum of one and a maximum of three stones per turn. The person who takes the last stone wins.

Assuming both of you are very smart and you start first, write an algorithm that takes a positive integer n as input and returns whether you can win (true or false).

For example, if there are 4 stones, the algorithm should return false. Because no matter if you take 1, 2, or 3 stones, your opponent can take the remaining stones in one turn, leaving you to lose.

Firstly, this problem can certainly be solved using dynamic programming, as there are obvious subproblems and they repeat. However, because both players are smart and it involves a game between you and your opponent, dynamic programming would be quite complex.

Our usual approach to such problems is to think in reverse:

If I can win, then when it's my turn to take stones, there must be 1 to 3 stones left, so I can take them all at once.

How to create such a situation? Obviously, if the opponent faces 4 stones, no matter how they take them, there will be 1 to 3 stones left, and I will win.

How to force the opponent to face 4 stones? I need to ensure that when it's my turn, there are 5 to 7 stones left, so I can make the opponent face 4 stones.

How to create a situation with 5 to 7 stones? Make the opponent face 8 stones; no matter how they take them, they will leave me with 5 to 7 stones, and I will win.

Continuing this loop, we find that as long as the number of stones is a multiple of 4, it's a trap. You can never escape the multiples of 4 and will always lose. Therefore, the solution to this problem is very simple:

boolean canWinNim(int n) {
    // If the initial number is a multiple of 4, just admit defeat
    // Otherwise, you can control the opponent to a multiple of 4 and ensure victory
    return n % 4 != 0;
}

bool canWinNim(int n) {
    // If the initial number is a multiple of 4, just admit defeat
    // Otherwise, you can control the opponent to a multiple of 4 and ensure a win
    return n % 4 != 0;
}

def canWinNim(n: int) -> bool:
    # If you step on a multiple of 4 right away, you might as well surrender
    # Otherwise, you can control the opponent to a multiple of 4 and win
    return n % 4 != 0

func canWinNim(n int) bool {
    // If the initial number is a multiple of 4, just admit defeat
    // Otherwise, you can control the opponent to a multiple of 4 and be sure to win
    return n % 4 != 0
}

var canWinNim = function(n) {
    // If the initial number is a multiple of 4, just admit defeat
    // Otherwise, you can control the opponent to a multiple of 4 and be sure to win
    return n % 4 !== 0;
}

II. Stone Game

The rules of LeetCode problem #877 "Stone Game" are as follows:

You and your friend are in front of a row of stone piles, represented by an array piles, where piles[i] indicates the number of stones in the i-th pile. You take turns picking stones, one pile at a time, but you can only take the pile from either the leftmost or rightmost end. The winner is the one who has more stones when all piles are taken.

Assuming both of you are very smart, and you start first, write an algorithm that takes an array piles as input and returns whether you can win (true or false).

Note that the number of stone piles is even, so both of you will end up taking the same number of piles. The total number of stones is odd, meaning it's impossible for both of you to end up with the same number of stones; there will definitely be a winner.

For example, if piles=[2, 1, 9, 5] and you start first, you can take either 2 or 5. You choose 2.

Now piles=[1, 9, 5], it's your opponent's turn, and they can take either 1 or 5. They choose 5.

Then piles=[1, 9] and it's your turn again, so you take 9.

Finally, your opponent is left with only 1.

In the end, you have a total of 2 + 9 = 11 stones, while your opponent has 5 + 1 = 6 stones. You can win, so the algorithm should return true.

As you can see, it's not just about picking the larger number. Why choose 2 instead of 5 at first? Because 5 is followed by 9. If you go for immediate gain, you expose the 9 pile to your opponent, and you might lose.

This is why it's emphasized that both players are smart; the algorithm seeks the optimal decision-making process to determine if you can win.

This problem involves a two-player game and can be solved using dynamic programming, which is quite complex. However, if we think deeply about the rules, we'll realize with surprise: if you are smart enough, you are guaranteed to win because you are the first to move.

boolean stoneGame(int[] piles) {
    return true;
}

bool stoneGame(vector<int>& piles) {
    return true;
}

def stoneGame(piles: List[int]) -> bool:
    return True

func stoneGame(piles []int) bool {
    return true
}

var stoneGame = function(piles) {
    return true;
}

The reason for this is that the problem has two important conditions: first, the total number of stone piles is even, and the total number of stones is odd. These two conditions, which seem to increase the fairness of the game, actually make it a game of exploiting others. Let's explain with piles=[2, 1, 9, 5], assuming these four piles are indexed from left to right as 1, 2, 3, and 4.

If we divide these four piles into two groups based on the odd and even indices, i.e., piles 1 and 3, and piles 2 and 4, the number of stones in these two groups will definitely be different. This means one group will have more stones than the other. Because the total number of stones is odd, it cannot be evenly divided.

As the first person to take stones, you can control whether you take all the even-indexed piles or all the odd-indexed piles.

You can initially choose either pile 1 or pile 4. If you want the even-indexed piles, you take pile 4. This leaves your opponent with only piles 1 and 3 to choose from. No matter how they take, pile 2 will be exposed for you to take next. Similarly, if you want the odd-indexed piles, you take pile 1, leaving your opponent with only piles 2 and 4. No matter how they take, pile 3 will be exposed for you.

In other words, you can observe in the first step whether the total number of stones in the odd-indexed piles is greater than or less than that in the even-indexed piles. Then, by planning your moves carefully, you can control the game entirely. Knowing this loophole allows you to outsmart unsuspecting players.

III. Light Switch Problem

The rules for LeetCode problem #319 "Bulb Switcher" are as follows:

There are n light bulbs, all initially turned off. We will perform n rounds of operations:

• In the 1st round, we toggle the switch of every bulb (turning them all on).
• In the 2nd round, we toggle the switch of every second bulb (i.e., bulbs 2, 4, 6, ..., which will be turned off).
• In the 3rd round, we toggle the switch of every third bulb (i.e., bulbs 3, 6, 9, ..., some will be turned off like bulb 3, and some will be turned on like bulb 6).

This pattern continues until the nth round, where we only toggle the switch of the nth bulb.

Given a positive integer n representing the number of bulbs, the task is to determine how many bulbs are on after n rounds of operations.

We could use a boolean array to represent the on/off state of these bulbs and simulate the entire process, then count the result. However, this approach lacks elegance. The optimal solution is as follows:

int bulbSwitch(int n) {
    return (int)Math.sqrt(n);
}

int bulbSwitch(int n) {
    return (int)sqrt(n);
}

def bulbSwitch(n: int) -> int:
    return int(n ** 0.5)

func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}

var bulbSwitch = function(n) {
    return Math.floor(Math.sqrt(n));
};

What? How is this problem related to square roots? Actually, the solution is quite clever. If no one tells you the solution, it might be hard to figure out.

First, since all the lights start off, a light that ends up being on must be toggled an odd number of times.

Let's assume there are only 6 lights, and we focus on the 6th light. We need to go through 6 rounds of operations, right? So, how many times will the 6th light be toggled? It's not hard to see that it will be toggled in the 1st, 2nd, 3rd, and 6th rounds.

Why are the 1st, 2nd, 3rd, and 6th rounds toggled? Because 6=1*6=2*3. Generally, factors come in pairs, meaning the switch is usually toggled an even number of times. However, there are special cases. For example, if there are 16 lights, how many times will the 16th light be toggled?

16 = 1*16 = 2*8 = 4*4

Here, the factor 4 appears twice, so the 16th light will be toggled 5 times, an odd number. Now you should understand why this problem is related to square roots.

But we want to find out how many lights are on at the end, right? What does taking the square root directly mean? Think about it a bit, and it will make sense.

Assume there are 16 lights. We take the square root of 16, which is 4. This means that at the end, 4 lights will be on. These are the lights at positions 1*1=1, 2*2=4, 3*3=9, and 4*4=16.

Even if the square root of some n is a decimal, converting it to an integer acts as an upper bound. All integers below this bound, when squared, will be the indices of the lights that are on at the end. So, directly converting the square root to an integer gives us the answer to this problem.