Problem 589099 · medium · Level 05 Advanced Algorithms & Graphs

Bits Shared by a Whole Ticket Range

bit manipulation · common prefix

Tickets are numbered lo, lo + 1, ..., hi. Return the bitwise AND of all ticket numbers in that inclusive range. The range can be enormous, so do not loop over it.

Examples

Input:  lo = 12, hi = 15
Output: 12
Explanation: 1100 & 1101 & 1110 & 1111 = 1100.

Input:  lo = 8, hi = 16
Output: 0

Constraints

  • 0 <= lo <= hi <= 10**18
  • Target complexity: O(log hi).

Goals

  • See that the answer is the common binary prefix of lo and hi
  • Find that prefix by shifting both ends until they agree
  • Run in O(log hi) regardless of the range length
Starting Python…