Problem:
Given an integer , find the number of 1 bits for every number (in binary form) starting from 0 to that integer.
Input:
8
Output:
[0,1,1,2,1,2,2,3,1]
For the number 8 , you need to find the number of 1 bits in the numbers 0,1,2,3,4,5,6,7,8 and store them in an output array in their respective index.
Try out the solution here:
https://leetcode.com/problems/counting-bits/
Solution:
The below post explains how to find the number of 1 bits in a single integer :
The time complexity for the above algorithm(the optimal one) is O(logn).
If you use the above algorithm for each number upto the given integer input n , then it will take O(nlogn) time .
A better solution exists which takes only O(n) time complexity.
Hint:
- When you divide a number by 2, it gets right shifted by 1 place and you loose the rightmost bit
Optimal Solution:
Let’s analyze the above hint:
If you divide a number by 2, it gets right shifted by 1 digit.
So if it is an even number , the last digit will be 0 , so the number of “1 bits” remain the same even after the division.
So ,
Number of 1 bits in a even number = Number of 1 bits in the even number divided by 2.
If it is an odd number , the last digit will be 1 , so on right shifting (dividing by 2) you loose the last “1 bit”. Hence the number of 1 bits in an odd number is one less than the number of 1 bits in an odd number divided by 2.
So,
Number of 1 bits in a odd number = Number of 1 bits in the odd number divided by 2 + 1.
Using these two concepts , you can write an algorithm which finds the solution in a single pass (O(n) time).
Here is the algorithm:
ALGORITHM:
STEP1: Initialize the first element of the output array to 0 (as the number of 1 bits in the element 0 is 0)
STEP2: For each element i from number 1 to the given integer n , find the number of 1 bits using the formula:
output[i] = output[i/2] for even numbers
output[i] = output[i/2] + 1 for odd numbers.
This can be represented in a single formula using :
output[i] = output[i/2] + (i%2)
i%2 will return 0 for even numbers and 1 for odd numbers.
STEP3: Return the output
Code:
class Solution {
public int[] countBits(int n) {
int[] output = new int[n+1];
output[0] = 0;
for(int i =1;i<=n;i++){
output[i]=output[i/2]+i%2;
}
return output;
}
}
The time complexity of above code is O(n) since we iterate through the for loop upto n times.
Space complexity is O(n) for the output array.
Leave a Reply