solution + explanation (using precalculated answers)


  • 1
    A

    Suppose we calculated answers for the numbers till X. Now, we want to compute answer for the number X. By removing any bit of X we will decrease the number, i.e. we can use answers which we've already calculated. One option to find any set bit of X is to track the most significant bit.

    More formally we come to recurrence relation as below

    bitcounts(i) = bitcounts(i-(2^mostSignificantBit)) + 1

    public class Solution {
        public int[] countBits(int num) {
            int bits[] = new int[num+1];
            int powerTwo = 1;
            int prevPos = 0;
            for (int i=1; i<=num; i++) {
                bits[i] = bits[prevPos]+1;
                prevPos++;
                if (prevPos==powerTwo) {
                    prevPos = 0;
                    powerTwo = powerTwo*2;
                }
            }
            return bits;
        }
    }
    

Log in to reply
 

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