Skip to content

3125. Maximum Number That Makes Result of Bitwise AND Zero πŸ”’

Description

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.

 

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

Solutions

Solution 1: Bit Manipulation

Thinking

We need the largest \(x\le n\) such that \(x\) AND \(x+1\) is \(0\). Trying \(n-1,n-2,\ldots\) is linear in the worst case.

\(x\) and \(x+1\) are consecutive, so their AND vanishes only when \(x\) is a string of low ones. The largest such value below \(n\) is the mask under \(n\)'s highest bit.

Return \(2^{\textit{bit\_length}(n)-1}-1\). It ANDs with its successor to zero and is maximal under \(n\).

We can find the highest bit of \(1\) in the binary representation of \(n\). The maximum \(x\) must be less than \(n\) and this bit is \(0\), and all other lower bits are \(1\), i.e., \(x = 2^{\textit{number of the highest bit}} - 1\). This is because \(x \textit{ and } (x + 1) = 0\) must hold.

The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def maxNumber(self, n: int) -> int:
        return (1 << (n.bit_length() - 1)) - 1

1
2
3
4
5
class Solution {
    public long maxNumber(long n) {
        return (1L << (63 - Long.numberOfLeadingZeros(n))) - 1;
    }
}

1
2
3
4
5
6
class Solution {
public:
    long long maxNumber(long long n) {
        return (1LL << (63 - __builtin_clzll(n))) - 1;
    }
};

1
2
3
func maxNumber(n int64) int64 {
    return int64(1<<(bits.Len64(uint64(n))-1)) - 1
}

Comments