You get a whole number n.
Return an array bits with n + 1 numbers. For each i, bits[i] is how many 1s the number i has in binary.
Example 1:
Input: n = 4 Output: [0,1,1,2,1] Explanation: Each number in binary: 0 is 0, with no 1s. 1 is 1, with one 1. 2 is 10, with one 1. 3 is 11, with two 1s. 4 is 100, with one 1.
Example 2:
Input: n = 8 Output: [0,1,1,2,1,2,2,3,1] Explanation: 7 is 111 in binary, so it has three 1s. 8 is 1000, so it has one 1.
Example 3:
Input: n = 0 Output: [0] Explanation: The only number is 0, and it has no 1s.
Constraints:
nis from 0 to 100,000.
Your algorithm should run in O(n) time, a constant amount of work per number, and use O(1) extra space besides the array 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 array, 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 array we return, we keep only the loop variable, so the extra space is O(1).
Free plan: 30 tutor messages. PRO is unlimited.
Saved
Ctrl + Enter to check
