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 <= 1015We 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^{number of the highest bit} - 1. This is because x and (x + 1) = 0 must hold.
The time complexity is O(log n), and the space complexity is O(1).
Java
C++
Go
LeetCode Day 23 - Bitwise AND of Numbers Range • Errichto Algorithms • 27,652 views views
Watch 9 more video solutions →Practice Maximum Number That Makes Result of Bitwise AND Zero with our built-in code editor and test cases.
Practice on FleetCode