DP solution beats 99% C#


  • 0

    Its known that powers of 2 only have one bit that is set.

    To find if a number is a power of 2, i & (i-1) == 0

    Say, bit i is set for a power of two, all the number after this set bit are values from 1 to 2 ^(i-1). Since we would have already evaluated the answer, we simply use it.

    public class Solution {
    
        public int[] CountBits(int num) {
    
            int[] count = new int[num+1];
    
            count[0] = 0;
    
            int iCount = 1;
    
            if (num > 0)
            {
                count[1] = 1;    
            }
    
            for(int i = 2; i <= num; i++)
            {
                if ((i & (i-1)) == 0)
                {
                    count[i] = 1;
                    iCount = 1;
                }
                else {
                    count[i] = 1 + count[iCount];
                    iCount++;
                }
            }
            
            return count;
        }
    }
    

Log in to reply
 

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