C# O(n) DP with comments


  • 0
    Y
    public class Solution {
        public int[] CountBits(int num) {
            int[] DP = new int[num+1];
            DP[0]=0;
            for(int i=1;i<num+1;i++)
            {
                //if i is even, then its 1s will be (i-1)'s 1s +1;
                if((i&1) == 1)
                    DP[i]=DP[i-1]+1;
               //if i is odd, then its 1s will be (i/2)'s 1s;
               else
                    DP[i]=DP[i/2];
            }
            return DP;
        }
    }

Log in to reply
 

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