Two solutions, by unset either the left most or the right most set bit


  • 0
    B

    Hello,

    The key of the problem is to reuse the value we have already calculated. It's not difficult to come up following 2 observations:

    A. count[i] = count[turn_off_the_left_most_set_bit_of_i(i)] + 1;
    

    or

    B. count[i] = count[turn_off_the_right_most_set_bit_of_i(i)] + 1;
    

    Both count[turn_off_the_left_most_set_bit_of_i(i)] and count[turn_off_the_right_most_set_bit_of_i(i)] are already calculated the time we want to calculate count[i], so the we are good to go.

    inline int turn_off_the_left_most_set_bit_of_i(int i) {
        return i - (1 << (int)log2(i));
    }
    
    inline int turn_off_the_right_most_set_bit_of_i(int i) {
        return i & (i-1);
    }
    
    vector<int> countBits(int num) {
        vector<int> count(num + 1, 0);
        count[0] = 0;
        for (int i = 1; i <= num; ++i) {
            count[i] = count[turn_off_the_right_most_set_bit_of_i(i)] + 1;
        }
        return count;
    }

  • 1
    B

    We can divide all numbers into two category, odd numbers and even numbers. If a is an even number, the number of 1s in a will be the same as the a/2, this is because we just shift the number without adding any 1s when we time a with 2. If it is an odd number, it will have one more 1 than its previous even number.

    public int[] countBits(int num) {
            if(num < 0) return new int[0];
            int[] counts = new int[num+1];
            counts[0] = 0;
            for(int i = 1; i < num+1; i++){
                if((i&1) != 0){
                    counts[i] = counts[i-1] + 1;
                }else{
                    counts[i] = counts[i/2];
                }
            }
            return counts;
        }

  • 0
    B

    @bargitta, the logic you used is more easier to deduce. Thanks for the sharing!


  • 0
    B

    glad u like it :)


Log in to reply
 

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