LeetCode 3125 - Maximum Number That Makes Result of Bitwise AND Zero

Difficulty: 🟡 Medium
Topics: String, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to find the largest integer x such that:

x <= n
The bitwise AND of every integer in the inclusive range [x, n] equals 0

In other words, we want the widest possible suffix ending at n whose cumulative bitwise AND becomes zero, while keeping x as large as possible.

For example, if n = 7, we examine ranges ending at 7:

[7] = 7
[6,7] = 6
[5,6,7] = 4
[4,5,6,7] = 4
[3,4,5,6,7] = 0

The first range that produces 0 starts at 3, so the answer is 3.

The constraint 1 <= n <= 10^15 is extremely important. Since 10^15 is far too large for any linear scan over values, we must derive a mathematical or bitwise observation that allows the answer to be computed in constant or logarithmic time.

The key challenge is understanding when a bitwise AND over a consecutive range becomes zero.

Several edge cases are important immediately:

Very small values such as n = 1
Powers of two such as 8, 16, 32
Numbers immediately after a power of two such as 9, 17
Numbers consisting entirely of 1 bits such as 7, 15, 31

These cases reveal the binary structure that determines the answer.

Approaches

Brute Force Approach

A direct approach is to try every possible starting point x from n down to 0.

For each candidate x, we compute:

x & (x+1) & (x+2) & ... & n

If the result becomes 0, we return that x.

This works because it explicitly checks the exact condition required by the problem. However, it is far too slow.

If we recompute the AND for every range independently, the time complexity becomes approximately:

O(n^2)

Even with optimizations, scanning ranges up to 10^15 is completely infeasible.

Key Insight

The crucial observation is that the bitwise AND of a consecutive range keeps only the common high-order prefix shared by all numbers in the range.

As soon as the range crosses a power-of-two boundary, some high bit changes from 0 to 1, which destroys all shared prefix bits and can force the AND to become zero.

Consider n = 13:

13 = 1101

The largest power of two less than or equal to 13 is 8:

8 = 1000

If we include numbers from 7 to 13:

No bit position remains 1 across the entire range, so the AND becomes 0.

This leads to the main observation:

The maximum valid x is always:

x = 2^k - 1

where 2^k is the highest power of two less than or equal to n.

Equivalently:

x = highestPowerOfTwo(n) - 1

Examples:

n	Highest Power of Two ≤ n	Answer
7	4	3
9	8	7
17	16	15

We can compute this efficiently using bit operations.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible range explicitly
Optimal	O(log n)	O(1)	Finds highest power of two using bit operations

Algorithm Walkthrough

Optimal Algorithm

Find the highest power of two less than or equal to n.

This can be done by repeatedly shifting left until the next power would exceed n. 2. Suppose that highest power is p.

Then:

p <= n < 2p

Return p - 1.

The range [p - 1, n] crosses the boundary between:

0xxxx...

and

1xxxx...

which guarantees the cumulative AND becomes zero.

Why it works

Any consecutive range whose AND is zero must include enough variation in bits so that every bit position becomes cleared at least once.

The moment a range crosses a power-of-two boundary, the most significant bit changes. Numbers below the boundary have that bit equal to 0, while numbers above it have that bit equal to 1.

The largest valid starting point is therefore the number immediately before the highest power of two not exceeding n, namely:

2^k - 1

No larger starting point can work because all numbers would share the same highest set bit, making the AND nonzero.

Python Solution

class Solution:
    def maxNumber(self, n: int) -> int:
        highest_power = 1
        
        while (highest_power << 1) <= n:
            highest_power <<= 1
        
        return highest_power - 1

The implementation starts with highest_power = 1 and repeatedly doubles it using a left shift.

The condition:

(highest_power << 1) <= n

checks whether the next power of two still fits within n.

Once the loop finishes, highest_power is the largest power of two less than or equal to n.

The answer is then simply:

highest_power - 1

which corresponds to the binary number containing all 1 bits below that power.

For example:

n = 17

highest_power = 16

answer = 15

because:

15 = 1111
16 = 10000
17 = 10001

and the AND of the range becomes zero.

Go Solution

func maxNumber(n int64) int64 {
    var highestPower int64 = 1

    for (highestPower << 1) <= n {
        highestPower <<= 1
    }

    return highestPower - 1
}

The Go implementation mirrors the Python version closely.

The main difference is explicit integer typing. Since the constraint allows values up to 10^15, we use int64 to avoid overflow issues.

Bit shifting works naturally with int64, and the algorithm remains constant-space and logarithmic-time.

Worked Examples

Example 1

Input:

n = 7

Binary representation:

7 = 111

Find highest power of two:

Iteration	highest_power
Start	1
Shift	2
Shift	4
Next shift would be 8 > 7	Stop

Now:

answer = 4 - 1 = 3

Check:

AND result:

Output:

Example 2

Input:

n = 9

Binary:

9 = 1001

Find highest power of two:

Iteration	highest_power
Start	1
Shift	2
Shift	4
Shift	8
Next shift would be 16 > 9	Stop

Compute:

answer = 8 - 1 = 7

Check range:

7 = 0111
8 = 1000
9 = 1001

AND:

Output:

Example 3

Input:

n = 17

Binary:

17 = 10001

Find highest power of two:

Iteration	highest_power
Start	1
Shift	2
Shift	4
Shift	8
Shift	16
Next shift would be 32 > 17	Stop

Compute:

answer = 16 - 1 = 15

Check:

15 = 01111
16 = 10000
17 = 10001

AND:

Output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	We repeatedly double the power of two
Space	O(1)	Only a few variables are used

The loop runs once per bit position. Since n <= 10^15, the number of iterations is at most about 50, making the algorithm extremely efficient.

Test Cases

solution = Solution()

assert solution.maxNumber(1) == 0      # Smallest possible input
assert solution.maxNumber(2) == 1      # Exact power of two
assert solution.maxNumber(3) == 1      # All bits set
assert solution.maxNumber(4) == 3      # Another power of two
assert solution.maxNumber(7) == 3      # Example 1
assert solution.maxNumber(8) == 7      # Power of two boundary
assert solution.maxNumber(9) == 7      # Example 2
assert solution.maxNumber(15) == 7     # All ones before next boundary
assert solution.maxNumber(16) == 15    # Exact power of two
assert solution.maxNumber(17) == 15    # Example 3
assert solution.maxNumber(31) == 15    # Larger all-ones value
assert solution.maxNumber(32) == 31    # Larger power of two
assert solution.maxNumber(100) == 63   # General case
assert solution.maxNumber(1024) == 1023 # Large power of two
assert solution.maxNumber(10**15) == (1 << 49) - 1 # Maximum constraint scale

Test Case Summary

Test	Why
`n = 1`	Smallest valid input
`n = 2`	Exact power of two
`n = 3`	Small all-ones binary number
`n = 4`	Boundary transition
`n = 7`	Provided example
`n = 8`	Power-of-two crossing
`n = 9`	Provided example
`n = 15`	All lower bits set
`n = 16`	Larger exact power of two
`n = 17`	Provided example
`n = 31`	Repeated binary pattern
`n = 32`	Another boundary case
`n = 100`	General non-boundary value
`n = 1024`	Large power of two
`n = 10^15`	Maximum-scale stress test

Edge Cases

One important edge case is when n itself is a power of two. For example, if n = 8, a buggy implementation might incorrectly return 8 or another nearby value. However, every number in [8,8] has the highest bit set, so the AND is still 8, not 0. The correct answer is 7, which forces the range to cross the power-of-two boundary.

Another tricky case is when n already consists entirely of 1 bits in binary form, such as 7 or 15. In these cases, it may appear that starting close to n could still produce zero, but the range must include the next lower binary region to clear all shared bits. The formula still correctly returns the previous all-ones value below the highest power of two.

A third important edge case is the minimum input n = 1. The only possible ranges are [1] and [0,1]. Since the AND of [1] is 1, the answer must be 0. The implementation handles this naturally because the highest power of two less than or equal to 1 is 1, and 1 - 1 = 0.

Finally, extremely large inputs near 10^15 could expose overflow or performance problems in naive implementations. The optimal solution avoids both issues because it performs only logarithmic-time bit shifts and uses integer types capable of storing all valid inputs.