338. Counting Bits

public class Solution {
    public int[] CountBits(int num) {
        int[] ans = new int[num + 1];
        for (int x = 1; x <= num; ++x) {
            ans[x] = ans[x & (x - 1)] + 1;
        }
        return ans;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& CountBits(int num) {
        vector<int>& ans = new int[num + 1];
        for (int x = 1; x <= num; ++x) {
            ans[x] = ans[x & (x - 1)] + 1;
        }
        return ans;
    }
}

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

var countBits = function(num) {
    let ans = new Array(num + 1).fill(0);
    for (let x = 1; x <= num; x++) {
        ans[x] = ans[x & (x - 1)] + 1;
    }
    return ans;
};

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

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

Algorithm

Инициализация arrayа:

Создайте array ans длиной n + 1, заполненный нулями. Этот array будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

Итерация и вычисление:

Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

Возврат результата:

return заполненный array ans, который содержит количество единиц для каждого числа от 0 до n.

😎