0338. Counting Bits

https://leetcode.com/problems/counting-bits

Description

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 <= 105

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?

• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

ac

class Solution {
    public int[] countBits(int num) {
        // edge cases
        if (num < 0) throw new IllegalArgumentException("invalid input");

        // dp
        int[] dp = new int[num+1];
        dp[0] = 0;
        int base = 1;

        for (int i = 1; i <= num; i++) {
            if (i / base == 2) {
                dp[i] = 1;
                base = base << 1;
            } else {
                int idx = i % base;
                dp[i] = dp[idx] + 1;
            }
        }

        return dp;
    }
}
/*
power
f[i]
state: f[i] bit counts at i point
func: 1) if i/pow(2, power) == 2, f[i] = 1, power++;
        2) idx = i % pow(2, power), f[i] = f[idx] + 1;
init: f[0] = 0, power = 0
ans: f
*/

ac2: bit manipulation

class Solution {
    public int[] countBits(int num) {
        // edge case
        if (num < 0) return new int[0];

        int[] dp = new int[num+1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i>>1] + (i&1);
        }

        return dp;
    }
}

ac3: bit manipulation

class Solution {
    public int[] countBits(int num) {
        // edge case
        if (num < 0) return new int[0];

        int[] dp = new int[num+1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i&(i-1)] + 1;
        }

        return dp;
    }
}