LeetCode 338: Counting Bits

Search for a command to run...

No comments yet. Be the first to comment.
Question Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. No...

class Solution { public: int missingNumber(vector<int>& nums) { int result = nums.size(); for (int i = 0; i < nums.size(); i++) { result ^= i ^ nums[i]; } return result; } }; Question Given an ar...

Problem Overview The goal is to write a function that takes an unsigned integer and returns the number of ‘1’ bits it has in its binary representation. This value is also known as Hamming weight. This is the classic bit manipulation problem. Solution...

Bruce Lin
4 posts
Given an integer n, return an array ans of length n + 1 where ans[i] is the number of set bits in the binary representation of i.
Example: n = 5 → Output: [0, 1, 1, 2, 1, 2]
Constraints: 0 <= n <= 10^5
This is the most intuitive approach. We iterate through each number from 0 to n, and for each number, we manually count its set bits.
The Algorithm for counting bits of a single number i:
Initialize a counter for the current number, e.g., count = 0.
Use a temporary variable temp_num = i to avoid modifying the main loop’s counter.
Use a while loop that continues as long as temp_num is not 0.
Check the LSB: Use the bitwise AND operator(&) to check if the least significant bit is a 1.
Shift to the Next Bit: Use the right shift operator (>>) to discard the LSB.
The loop terminates when the number becomes 0.
C++ implementation:
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1);
for (int i = 0; i <= n; ++i) {
// Logic to count bits for each number 'i'
int count = 0;
int temp_num = i;
while (temp_num != 0) {
if ((temp_num & 1) == 1) { // or simply: if (temp_num & 1)
count++;
}
temp_num = temp_num >> 1;
}
ans[i] = count;
}
return ans;
}
};
Complexity Analysis:
Time Complexity: O(n * log(n))
The outer for loop runs n + 1 times.
The inner while loop runs for a number of times equal to the number of bits in i, which is approximately log(i).
Space Complexity: O(n)
ans array that we return.