Maximum Number That Makes Result of Bitwise AND Zero

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:

1
2
3
4
5
6
7


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:

1
2
3
4


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

Example 3:

1
2
3
4


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

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

Code

1
2
3
4
5
6
7
8


class Solution {
public:
    int maximumX(int n) {
        int p = 1;
        while (p <= n) p <<= 1;
        return p - n - 1;
    }
};

1
2
3
4
5
6
7


func maximumX(n int) int {
    p := 1
    for p <= n {
        p <<= 1
    }
    return p - n - 1
}

1
2
3
4
5
6
7


class Solution {
    public int maximumX(int n) {
        int p = 1;
        while (p <= n) p <<= 1;
        return p - n - 1;
    }
}

1
2
3
4
5
6
7


class Solution {
    fun maximumX(n: Int): Int {
        var p = 1
        while (p <= n) p = p shl 1
        return p - n - 1
    }
}

1
2
3
4
5
6


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

1
2
3
4
5
6
7
8
9


impl Solution {
    pub fn maximum_x(n: i32) -> i32 {
        let mut p = 1;
        while p <= n {
            p <<= 1;
        }
        p - n - 1
    }
}

1
2
3
4
5
6
7


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.

Problem#

Examples#

Solution#

Method 1 – Bitwise Greedy#

Intuition#

Approach#

Code#

Complexity#