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

• 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;
}``````

• 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;
}``````

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

• glad u like it :)

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