Simple Java O(n) solution using two pointers


  • 62
    A

    This uses the hint from the description about using ranges. Basically, the numbers in one range are equal to 1 plus all of the numbers in the ranges before it. If you write out the binary numbers, you can see that numbers 8-15 have the same pattern as 0-7 but with a 1 at the front.

    My logic was to copy the previous values (starting at 0) until a power of 2 was hit (new range), at which point we just reset the t pointer back to 0 to begin the new range.

    public int[] countBits(int num) {
        int[] ret = new int[num+1];
        ret[0] = 0;
        int pow = 1;
        for(int i = 1, t = 0; i <= num; i++, t++) {
            if(i == pow) {
                pow *= 2;
                t = 0;
            }
            ret[i] = ret[t] + 1;
        }
        return ret;
    }

  • 1
    X

    Great Solution! Thank you for sharing!


  • 0
    W

    Much easier to understand. Good job.


  • 1
    E

    My Solution:

    public class Solution {
        public int[] countBits(int num) {
            int[] result = new int[num+1];
            result[0] = 0;
            for(int i=1;i<=num;i++){
                if(i%2!=0) result[i] = result[i-1]+1;
                else if(1073741824%i==0) result[i] = 1;
                else result[i] = result[i/2];
            }
            return result;
        }
    }
    

  • 0
    E

    My thought is the same as yours, but in different way:

    public class Solution {
        public int[] countBits(int num) {
            //这题主要是动态规划,也就是后面的个数可以通过前面得到的计算
            if (num < 1)
            return new int[] {0};
            
            int [] count = new int[num+1];
            count[0] = 0;
    
            int k = 0;
    
            for (int i = 1; i <= num;) {
                    k = i;
                    for (int j =0; j < i; j++) {
                        if (k <= num) {
                            count[k++] = count[j] + 1;
                        } 
                    }
                    if (k > num) 
                    break;
                    i = k;
                    
              //  }
            }
           // ret:
            return count;
                }
    }
    

  • 0

    Thanks for sharing! Here is my similar thought without variable t though (maybe slightly slower than yours but more concise). I assume the solution of this problem is much alike that of Gray Code.

        public int[] countBits(int num) {
            int[] bit1s = new int[num + 1];
            for (int i = 1, j = 1; i <= num; i++) {
                if (i == j * 2) {
                    j <<= 1;
                }
                bit1s[i] = bit1s[i - j] + 1; // assert: i - j >= 0
            }
            return bit1s;
        }
    

  • 1
    W

    This technique is similar to Brent's Cycle Detection algorithm.

        if(i == pow) {
            pow *= 2;
            t = 0;
        }

  • 0
    C

    @Alderdragon Genius~


Log in to reply
 

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