Почему это работает
- Посмотрим на одну позицию бита. Каждое число из тройки даёт там 0 или 3 единицы, так что тройки вместе дают число, кратное 3. Число без тройки добавляет сверху 1 или 0, и ones % 3 показывает, что именно.
- Биты не смешиваются: каждая позиция считается отдельно, и позиции, где ones % 3 = 1, — ровно единичные биты ответа. В столбце 0 две тройки дают 6 единиц, а 6 % 3 = 0.
- Обычный xor здесь не работает: три копии числа переключают его биты три раза и оставляют одну копию. Здесь xor всех чисел равен 0, а не 6.
Сложность
Время O(w · n), где w — ширина: по проходу по числам на каждый бит, на LeetCode w = 32, то есть O(n). Память O(1): счётчик и ответ.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗