Counting Bits Solution for Wipro
Company: Wipro · Difficulty: Medium · Topics: Dynamic Programming, Bit Manipulation
Problem Statement
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Examples
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Approach
Dynamic Programming with Bit Manipulation (Optimal)
1. Use the relationship: ans[i] = ans[i >> 1] + (i & 1)
2. Right shift removes the least significant bit
3. (i & 1) adds 1 if the LSB is 1, 0 otherwise
Time and Space Complexity
- Time Complexity: O(n) - Single pass through numbers
- Space Complexity: O(1) - Not counting output array