Accepted Java Solution Using Simple Arithmatic


  • 0
    L
    public class Solution {
        public int[] countBits(int num) {
            int[] bitMap = new int[num + 1]; //space complexity n
            bitMap[0] = 0;
            int pow = 0;
            int power = (int)Math.pow(2,pow);
            for(int idx = 1; idx <= num; idx++){
                if(idx == power){
                    bitMap[idx] = 1;
                    power = (int)Math.pow(2,++pow);
                }else{
                    int addend1 = idx - (int)Math.pow(2,pow-1);
                    int addend2 = idx - addend1;
                    bitMap[idx] = bitMap[addend1] + bitMap[addend2];
                }
            }
            return bitMap;
        }
    }

Log in to reply
 

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