338. Counting bits

338_solution1_clear.c

#include <stdlib.h>

int *countBits(int n, int *returnSize) {
  int *ans = calloc(n + 1, sizeof(int));
  for (int i = 1; i <= n; i++) {
    ans[i] = ans[i & (i - 1)] + 1;
  }
  *returnSize = n + 1;
  return ans;
}

338_solution2_shift.c

#include <stdlib.h>

int *countBits(int n, int *returnSize) {
  int *ans = calloc(n + 1, sizeof(int));
  for (int i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  *returnSize = n + 1;
  return ans;
}

338_solution1_clear.cpp

#include <vector>

using namespace std;

class Solution {
public:
  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;
  }
};

338_solution2_shift.cpp

#include <vector>

using namespace std;

class Solution {
public:
  vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
      ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
  }
};

338_solution1_clear.go

package bitmanipulation

func countBits(n int) []int {
    ans := make([]int, n+1)
    for i := 1; i <= n; i++ {
        ans[i] = ans[i&(i-1)] + 1
    }
    return ans
}

338_solution2_shift.go

package bitmanipulation

func countBits(n int) []int {
    ans := make([]int, n+1)
    for i := 1; i <= n; i++ {
        ans[i] = ans[i>>1] + (i & 1)
    }
    return ans
}

338_solution1_clear.java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i & (i - 1)] + 1;
        }
        return ans;
    }
}

338_solution2_shift.java

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

338_solution1_clear.js

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i & (i - 1)] + 1;
  }
  return ans;
};

338_solution2_shift.js

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
};

338_solution1_clear.py

from typing import List


class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i & (i - 1)] + 1
        return ans

338_solution2_shift.py

from typing import List


class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

338_solution1_clear.rs

impl Solution {
    pub fn count_bits(n: i32) -> Vec<i32> {
        let n = n as usize;
        let mut ans = vec![0; n + 1];
        for i in 1..=n {
            ans[i] = ans[i & (i - 1)] + 1;
        }
        ans
    }
}

338_solution2_shift.rs

impl Solution {
    pub fn count_bits(n: i32) -> Vec<i32> {
        let n = n as usize;
        let mut ans = vec![0; n + 1];
        for i in 1..=n {
            ans[i] = ans[i >> 1] + (i & 1) as i32;
        }
        ans
    }
}