Почему это работает
- Когда считаешь от left до right, у числа сначала меняются младшие биты, потом старшие. Ниже старшего бита, где left и right различаются, какое-то число между ними кончается одними нулями (здесь 28 = 11100), поэтому все такие биты в AND равны 0.
- Выше этого бита left и right совпадают, и у всех чисел между ними там те же биты, поэтому AND их сохраняет. Сдвиг обоих вправо, пока они не сравняются, находит ровно это общее начало.
- Сдвиг обратно на shift ставит начало на место и заполняет отброшенные столбцы нулями. Числа между left и right не читаются, поэтому диапазон может быть сколь угодно длинным.
Сложность
Время O(log right): по сдвигу на бит, на LeetCode не больше 31. Память O(1): три числа.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗