Simple Java O(n) Solution


  • 0
    S

    Two types of numbers are possible -

    1. Power of 2 -
      They have 1 bit because i & (i-1) == 0.
    2. Not Power of 2 -
      Expression ans[i & (i-1)] gives the number of bit of number having one bit less than it.
    class Solution {
        public int[] countBits(int num) {
            int[] ans = new int[num+1];
            ans[0] = 0;
            for(int i=1;i<=num;i++) 
                 ans[i] += ans[i & (i-1)] + 1;  
            return ans;     
        }
    }
    

Log in to reply
 

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