A C# solution.


  • 1
    V
    public class Solution {
        public int[] CountBits(int num) {
            int[] counts = new int[num+1];
            for(int i = 1; i < counts.Length; i++)
            {
                counts[i] = counts[i/2] + (i % 2);
            }
            return counts;
        }
    }
    

  • 1
    G

    This is the best solution I've seen so far. But, I am not able to figure out what approach would lead to this solution. What was your thought process?

    Edit 1: I see what's going on. Bit-shifting to the left doubles the number, keeping the number of 1s the same. If its an odd number, just add one more bit to the end with (i % 2). Brilliant!

    Edit 2: Just saw the top voted answer too. Exact same concept, implemented with bit manipulation.


Log in to reply
 

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