Given an integer n, return a vector bits of n + 1 numbers where, for every i from 0 to n, bits[i] is the number of 1 bits in the binary representation of i.
Example 1:
Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10
Example 2:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
Example 3:
Input: n = 0 Output: [0] Explanation: The only number is 0, and it has no 1 bits.
Constraints:
0 <= n <= 105
Your algorithm should run in O(n) time, a constant amount of work per number, and use O(1) extra space besides the vector it returns.
Shifting a number one place to the right drops its last bit: 13 is
1101, and 13 shifted right is 110, which is 6. So 13 has the 1 bits of 6, plus its own last bit.
Fill the answer from 0 up to
n. When you reach i, the count of i shifted right by one is already in the vector, because that number is smaller than i. Add the last bit of i, which is i AND 1: 1 when i is odd, 0 when it is even.
Each number from 1 to
n takes one step: O(n) time.Apart from the vector we return, we keep only the loop variable, so the extra space is O(1).
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
