C# - DP solution repeat every power of 2


  • 0

    The idea is every power of 2 call this N, the answer to the next N integers is 1 plus the answer at current - N.

        public int[] CountBits(int num) 
        {
            int[] bits = new int[num + 1];
            int curr = 1;
            int max = 1;
            while (curr <= num)
            {
                int prev = 0;
                while (curr <= num && curr < max)
                {
                    bits[curr] = 1 + bits[prev];
                    prev++;
                    curr++;
                }
                
                max *= 2;
            }
            return bits;
        }
    

Log in to reply
 

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