problemmediumalgorithmsleetcode-3125leetcode 3125leetcode3125

Maximum Number That Makes Result of Bitwise AND Zero

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Given an integer n, return the maximum integer x such that x <= n, and the bitwise AND of all the numbers in the range [x, n] is 0.

Examples

Example 1:

Input: n = 7
Output: 3
Explanation:
The bitwise `AND` of `[6, 7]` is 6.  
The bitwise `AND` of `[5, 6, 7]` is 4.  
The bitwise `AND` of `[4, 5, 6, 7]` is 4.  
The bitwise `AND` of `[3, 4, 5, 6, 7]` is 0.

Example 2:

Input: n = 9
Output: 7
Explanation:
The bitwise `AND` of `[7, 8, 9]` is 0.

Example 3:

Input: n = 17
Output: 15
Explanation:
The bitwise `AND` of `[15, 16, 17]` is 0.

Constraints:

  • 1 <= n <= 1015

Solution

Method 1 – Bitwise Greedy

Intuition

To make the bitwise AND of [x, n] equal to 0, we need to ensure that every bit position is zeroed out in the AND. The smallest power of two greater than n will have all lower bits set in the range [x, n] for some x. The answer is the smallest x such that [x, n] covers a full power of two, i.e., x = n + 1 - 2^k where 2^k is the smallest power of two greater than n.

Approach

  1. Find the smallest power of two greater than n (let's call it p).
  2. The answer is x = p - n - 1.
  3. Return x.

Code

C++
class Solution {
public:
    int maximumX(int n) {
        int p = 1;
        while (p <= n) p <<= 1;
        return p - n - 1;
    }
};
Go
func maximumX(n int) int {
    p := 1
    for p <= n {
        p <<= 1
    }
    return p - n - 1
}
Java
class Solution {
    public int maximumX(int n) {
        int p = 1;
        while (p <= n) p <<= 1;
        return p - n - 1;
    }
}
Kotlin
class Solution {
    fun maximumX(n: Int): Int {
        var p = 1
        while (p <= n) p = p shl 1
        return p - n - 1
    }
}
Python
class Solution:
    def maximumX(self, n: int) -> int:
        p = 1
        while p <= n:
            p <<= 1
        return p - n - 1
Rust
impl Solution {
    pub fn maximum_x(n: i32) -> i32 {
        let mut p = 1;
        while p <= n {
            p <<= 1;
        }
        p - n - 1
    }
}
TypeScript
class Solution {
    maximumX(n: number): number {
        let p = 1;
        while (p <= n) p <<= 1;
        return p - n - 1;
    }
}

Complexity

  • ⏰ Time complexity: O(log n) — We find the next power of two.
  • 🧺 Space complexity: O(1) — Only a few variables are used.

Comments