Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's 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
Constraints:
0 <= n <= 105Follow up:
O(n log n). Can you do it in linear time O(n) and possibly in a single pass?__builtin_popcount in C++)?program main
implicit none
integer :: n, ans(n+1)
! Example 1
n = 2
call solve(n, ans)
write(*,*) "Example 1:"
write(*,*) "n = ", n
write(*,*) "ans = ", ans
! Example 2
n = 5
call solve(n, ans)
write(*,*) "Example 2:"
write(*,*) "n = ", n
write(*,*) "ans = ", ans
contains
subroutine solve(n, ans)
implicit none
integer, intent(in) :: n
integer, intent(out) :: ans(n+1)
integer :: i
do i=0, n
ans(i+1) = count_ones(i)
end do
end subroutine solve
end program main
function count_ones(n) result(num_ones)
implicit none
integer, value :: n
integer :: num_ones
integer :: mask
mask = 1
do while (mask <= n)
if (mod(n, mask) == 0) then
num_ones = num_ones + 1
end if
mask = mask * 2
end do
end function count_onestemp.f95:4:26:
4 | integer :: n, ans(n+1)
| 1
Error: Explicit shaped array with nonconstant bounds at (1)
temp.f95:8:21:
8 | call solve(n, ans)
| 1
Error: Symbol ‘ans’ at (1) has no IMPLICIT type
temp.f95:7:5:
7 | n = 2
| 1
Error: Symbol ‘n’ at (1) has no IMPLICIT type
temp.f95:30:33:
30 | ans(i+1) = count_ones(i)
| 1
Error: Return type mismatch of function ‘count_ones’ at (1) (UNKNOWN/INTEGER(4))
temp.f95:30:23:
30 | ans(i+1) = count_ones(i)
| 1
Error: Function ‘count_ones’ at (1) has no IMPLICIT type
module binary_ones
implicit none
private
public :: binary_ones_array
contains
function binary_ones_array(n) result(ans)
integer, intent(in) :: n
integer :: i, j, ans(n+1)
do i = 0, n
ans(i) = 0
end do
do i = 1, n
do j = 1, i
ans(i) = ans(i) + mod(i, 2)
end do
end do
end function binary_ones_array
end module binary_ones
program test_binary_ones
use binary_ones
implicit none
integer :: n, i
integer, allocatable :: ans(:)
n = 2
ans = binary_ones_array(n)
write (*,*) ans
n = 5
ans = binary_ones_array(n)
write (*,*) ans
n = 10
ans = binary_ones_array(n)
write (*,*) ans
end program test_binary_ones
1 0 0
1 0 3 0 5 0
1 0 3 0 5 0 7 0 9 0 0
def countBits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i & (i - 1)] + 1
return ans
The algorithm leverages a key observation: (i & (i - 1)) has the same binary representation as i, but with the least significant 1 bit removed. This leads to a fast and efficient way to count the number of 1 bits in the binary representation of each number in the range [0, n].
For each number i in the range [1, n], we calculate ans[i] based on ans[i & (i - 1)]. Since ans[i & (i - 1)] is the count of 1 bits in the binary representation of (i & (i - 1)), adding 1 to that count will give us the count of 1 bits in the binary representation of i.
The algorithm iterates through the range [1, n] and fills the output array ans accordingly. The final array ans contains the count of 1 bits in the binary representation of each number in the range [0, n].
The time complexity of this algorithm is O(n) as it iterates through the range [1, n] only once, and the space complexity is O(n + 1) since it creates an array of length n + 1 to store the results.
#include <vector>
using namespace std;
vector<int> countBits(int n) {
vector<int> ans(n + 1, 0);
for (int i = 1; i <= n; ++i) {
ans[i] = ans[i & (i - 1)] + 1;
}
return ans;
}
The algorithm leverages a key observation: (i & (i - 1)) has the same binary representation as i, but with the least significant 1 bit removed. This leads to a fast and efficient way to count the number of 1 bits in the binary representation of each number in the range [0, n].
For each number i in the range [1, n], we calculate ans[i] based on ans[i & (i - 1)]. Since ans[i & (i - 1)] is the count of 1 bits in the binary representation of (i & (i - 1)), adding 1 to that count will give us the count of 1 bits in the binary representation of i.
The algorithm iterates through the range [1, n] and fills the output array ans accordingly. The final array ans contains the count of 1 bits in the binary representation of each number in the range [0, n].
The time complexity of this algorithm is O(n) as it iterates through the range [1, n] only once, and the space complexity is O(n + 1) since it creates an array of length n + 1 to store the results.