Welcome to Subscribe On Youtube
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 <= 10^{15}
Solutions
Solution 1: Bit Manipulation
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^{\text{number of the highest bit}}  1$. This is because $x \text{ and } (x + 1) = 0$ must hold.
The time complexity is $O(\log n)$, and the space complexity is $O(1)$.

class Solution { public long maxNumber(long n) { return (1L << (63  Long.numberOfLeadingZeros(n)))  1; } }

class Solution { public: long long maxNumber(long long n) { return (1LL << (63  __builtin_clzll(n)))  1; } };

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

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