Java O(n) Solution: 3ms


  • 0
    Y
    public class Solution {
        public int[] countBits(int num) {
            int[] result = new int[num + 1];
            for (int i = 1; i <= num; i++) {
                // Obviously, 
                // if i is even, then it should be i / 2 + "0"
                // if i is odd, it should be i / 2 + "1"
                // e.g.   8 --> 1000, 16 --> 1000 0, 17 --> 1000 1
                result[i] = result[i / 2] + i % 2;
            }
            return result;
        }
    }
    

Log in to reply
 

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