338.Counting Bits

Posted on | In

Solution 1: accepted 3ms

DP.

  1. Base case: M[0] = 0;
  2. Induction rule: M[i] = M[i - 2^n] + 1, n = the max possible n <= i

Time: O(n)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] countBits(int num) {
    int[] result = new int[num + 1];
    result[0] = 0;
    int next = 1; // 2^0
    int flag = 0; // when digit increases (2^n), we restart from the first position
    for (int i = 1; i <= num; i++) {
        if (i == next) {
            flag = 0;
            next *= 2; // 2^(n+1), each will add one more digit
        } 
        result[i] = 1 + result[flag];
        flag++;
    }
    return result;
}