C# solution with explanation


  • 0
    K

    I used this hint:
    2.Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
    If we look at the numbers
    num------#of 1 bits
    1 ----------->1

    2 ----------->1
    3 ----------->2

    4 ----------->1
    5 ----------->2
    6 ----------->2
    7 ----------->3

    For each range, we take the numbers and number+1 from the previous range and add to the list sequentially. First we take 1, and we add 1 and 2, then we take 1,2 and we add 1,2,2,3, and so on so forth..
    Since this type of adding goes as powers of 2, we do not need need to add all of the last range, we stop the loops if we reached num.(list.Count <= num)

    public class Solution {
        public int[] CountBits(int num) {
            List<int> list = new List<int>();
            list.Add(0);
            if (num == 0) return list.ToArray();
            list.Add(1);
            if (num == 1) return list.ToArray();
            int k = 1;
            while (list.Count<=num) {
                int count =list.Count; 
                for (int i=k;i < count && list.Count <= num;i++)
                    list.Add(list[i]);
                for (int i=k;i < count && list.Count <= num;i++) 
                    list.Add(list[i]+1);
                k *= 2;
            }
            return list.ToArray();
        }
    }
    

Log in to reply
 

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