C# O(n) DP solution with explanation


  • 0
    W

    If you look at the binary table progression it's evident that at each power of two, the number of ones progression is equal to the number of ones starting from 0 up to the current index plus one (check out the Binary Progression below). Therefore, our algorithm will iterate starting at 1, and keep building up our bit count array by 2x every progression until we reach our expected num.

    Binary Progression
    0	  0
    1	  1  <- index(0)+1
    2	 10  <- index(0)+1
    3	 11  <- index(1)+1 
    4	100  <- index(0)+1
    5	101  <- index(1)+1
    6	110  <- index(2)+1
    7	111  <- index(3)+1
    8      1000  <- index(0)+1
    
    public int[] CountBits(int num) {
        int[] bitCount = new int[num+1];
        for(int i=1; i<=num; i *= 2) {
            for(int j=0; j<i && j+i<=num; j++) {
                bitCount[i+j] = 1+bitCount[j];
            }
        }
        return bitCount;
    }
    

Log in to reply
 

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