🧩 Alice and Bob’s Binary Game — Full Intuition Walkthrough

Welcome to today’s blog! Let’s solve an interesting coding problem step by step, with full intuition, question details, and multiple solutions. This post is designed like a work-class learning blog so that even freshers can follow easily.

---

❓ The Question

There are two friends — Alice and Bob. They love binary numbers, but in different ways:

• Alice loves set bits at even positions (positions 0,2,4,… from the right).

• Bob loves set bits at odd positions (positions 1,3,5,…).

For a given number N:

• Each set bit contributes its value as 2^position.

• Alice sums values at even positions.

• Bob sums values at odd positions.

• Finally, we calculate the absolute difference between Alice’s and Bob’s scores.

Constraints

• 0 ≤ N ≤ 10^18

• Expected Time Complexity: O(log N)

• Expected Space Complexity: O(1)

Example 1

Input: N = 13
Binary: 1101

• Alice: (positions 0,2) → 1 + 4 = 5

• Bob: (position 3) → 8
  Output: |5 - 8| = 3

Example 2

Input: N = 42
Binary: 101010

• Alice: (even positions) = 0

• Bob: (positions 1,3,5) → 2 + 8 + 32 = 42
  Output: |0 - 42| = 42

---

🔍 Step-by-Step Intuition

The game is just about splitting binary bits into two groups:

• Even bits → Alice

• Odd bits → Bob

Then, sum their values and take the difference.

Think of it like sorting coins into two baskets — one basket for Alice (even slots), another for Bob (odd slots).

---

🥇 Solution 1: Bit-by-Bit Approach (For Freshers)

This solution mimics the game directly:

1. Start at the least significant bit (position 0).

2. Check if the bit is set.

3. Add it to Alice’s or Bob’s total based on position.

4. Move to the next bit until N = 0.

Code

public static long gameDifference(long N) {
    long aliceSum = 0, bobSum = 0;
    int pos = 0;

    while (N > 0) {
        if ((N & 1) == 1) {
            if (pos % 2 == 0) aliceSum += 1L << pos;
            else bobSum += 1L << pos;
        }
        N >>= 1;
        pos++;
    }
    return Math.abs(aliceSum - bobSum);
}

Intuition

• N & 1 checks if the current bit is set.

• pos % 2 decides whose turn it is (Alice or Bob).

• 1L << pos gives the actual value of that bit.

This solution is easy to follow and great for beginners.

---

🥈 Solution 2: Bitmask Trick (Easy & Fast)

Instead of looping through all bits, we can use bitmasks to directly separate Alice’s and Bob’s contributions.

👉 Think of the binary number as a checkerboard:

• Alice picks from the white squares → even positions → 0101... pattern.

• Bob picks from the black squares → odd positions → 1010... pattern.

These patterns can be represented using hexadecimal masks:

• Alice’s mask (even) = 0x5555555555555555L

• Bob’s mask (odd) = 0xAAAAAAAAAAAAAAAAL

Code

public static long gameDifference(long N) {
    long evenMask = 0x5555555555555555L; // Alice: 0,2,4...
    long oddMask  = 0xAAAAAAAAAAAAAAAAL; // Bob: 1,3,5...

    long aliceSum = N & evenMask;
    long bobSum   = N & oddMask;

    return Math.abs(aliceSum - bobSum);
}

How to Remember:

• 5 = 0101 → Alice’s mask (even positions).

• A = 1010 → Bob’s mask (odd positions).

📝 Just recall: Alice = 5, Bob = A.

---

⚡ Complexity Analysis

• Solution 1: O(log N) time, O(1) space.

• Solution 2: O(1) time, O(1) space.

---

🚀 Final Thoughts

• For freshers, use the bit-by-bit approach. It builds your fundamentals of bit manipulation.

• For experienced coders, the bitmask trick is elegant, fast, and easy to recall with the mnemonic “Alice = 5, Bob = A.”

Both solutions give the same result ✅ — choose the one that best suits your style of thinking.