Java O(n) time & space complexity 3 rows & 3 ms solution using DP


  • 1
    S

    Number of bits for n will be number of common bits in n and n-1 plus 1 (as diff between numbers is 1)

    for example 3(0 1 1) and 4(1 0 0) have 0 common bits (0 0 0) this is number 0 so for 4 will be 0+1 bit

    next, 4(1 0 0) and 5 (1 0 1) have 1 common bit (1 0 0) this is 4
    and we already have number of bits calculated for number 4 in the array, so for 5 will be 1 + 1 bits

    public int[] countBits(int num) {
        int[] bits = new int[num+1];
        for(int i = 1; i<= num; i++){
            bits[i]=bits[i-1 & i] + 1;
        }
        return bits;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.