algoadvance

Leetcode 3232. Find if Digit Game Can Be Won

Problem Statement

You are given a game where a two-player game starts with a positive integer n. The players take turns performing the following operation: subtract from n the largest power of 2 less than or equal to n. The player who cannot make a move loses the game. You need to determine if the starting player can force a win given that both players play optimally.

Clarifying Questions

1. What is the range of input n?
   • Assume 1 <= n <= 10^9.
2. What should be the output format?
   • Return true if the starting player can force a win; otherwise, return false.
3. Can we assume that both players know the optimal strategy?
   • Yes, both players play optimally.

Strategy

To determine if the starting player can force a win, we need to observe the pattern that occurs as powers of 2 are subtracted from n.

1. Calculate the Largest Power of 2: For a given n, we need to determine the largest power of 2 less than or equal to n. This can be done using bitwise operations.
2. Turn Simulation: By recursively or iteratively simulating the game, we can track whose turn it is and whether they win or lose.
3. Optimal Play Observation: By observing simple cases, we can deduce that if n is a power of 2, the second player always wins, because the first player will reduce n to 0 in their turn.

An efficient approach:

• If n is found to be of the form n = 2^k, the first player always loses.
• If n is not a power of 2, the first player has a strategy to make it 2^k in subsequent moves.

We can achieve this reasoning with the following implementation.

Code

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

bool canWinDigitGame(int n) {
    return (n & (n - 1)) != 0;
}

int main() {
    int n;
    cout << "Enter the number: ";
    cin >> n;

    if(canWinDigitGame(n)) {
        cout << "Starting player can force a win." << endl;
    } else {
        cout << "Starting player cannot force a win." << endl;
    }

    return 0;
}

Explanation

The function canWinDigitGame checks if n is a power of 2:

• Bit Manipulation Trick: (n & (n - 1)) is 0 if and only if n is a power of 2. This is because powers of 2 have only one bit set in their binary representation.
• Return true if the result is non-zero, meaning n is not a power of 2 and the first player can force a win.

Time Complexity

• The time complexity of determining if n is a power of 2 using the bit manipulation trick is O(1). This is because the operation involves just a couple of bitwise operations, and these are constant-time operations.

This solution is optimal and provides quick determination of the winning strategy for the starting player.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?