Shared Bits of a Range
MediumBit Manipulation
Problem
A permissions system assigns each account in the ID range [low, high] a bitmask equal to its own ID. To find the permissions every account in the range shares, the system ANDs all of those IDs together.
Return low AND (low + 1) AND … AND high. The range can contain billions of IDs, so do not iterate over it.
Example 1
- Input:
- low = 5, high = 7
- Output:
- 4
101 & 110 & 111 = 100.
Example 2
- Input:
- low = 12, high = 15
- Output:
- 12
Example 3
- Input:
- low = 1, high = 2147483647
- Output:
- 0
Constraints
- 0 ≤ low ≤ high < 2^31
Hint
Show the first hint
If any bit flips somewhere between low and high, it cannot survive the AND.
Walkthrough
How to approach it
01Clarify before coding
- Is the range inclusive? Yes, both ends are included.
- Can low equal high? Yes, then the answer is low itself.
02Brute force
Start with low and AND in every ID up to high.
Cost: O(high - low) time, up to 2 · 10^9 operations: far too slow.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.