Код Middle Биты обновлено
Число единичных битов
Условие
Для каждого i от 0 до n верни количество единиц в его двоичной записи.
Примеры
countBits(5) // [0, 1, 1, 2, 1, 2]
countBits(0) // [0]
countBits(2) // [0, 1, 1]
Как подойти
Связка битовых операций и динамики: сдвиг вправо убирает младший бит, а сам он даётся как i & 1. Получается O(n) вместо O(n log n) при подсчёте битов каждого числа отдельно.
Подсказки: 2
- Число i отличается от i >> 1 ровно младшим битом.
- Это динамика, а не перебор битов каждого числа.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.