algoadvance

Leetcode 338. Counting Bits

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.

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

Constraints:

• 0 <= n <= 10^5

Clarifying Questions

1. Q: Should we consider the binary representation length or only the count of 1s? A: Only the count of 1s in the binary representation of each integer from 0 to n.

2. Q: Are there any restrictions on time or space complexity? A: The solution should be efficient in both time and space, preferably O(n) for time complexity and O(n) for space complexity.

Strategy

We can utilize dynamic programming to solve this problem. Let’s break down our approach:

1. Base Case: The number of 1s for 0 is 0.

2. General Case: For any integer i, the number of 1s in i can be derived from its half (i/2):

   • If i is even, i has the same number of 1s as i/2.
   • If i is odd, i has one more 1 than i/2.

Thus, we can use the following recurrence relation to populate our ans array:

• ans[i] = ans[i >> 1] + (i & 1)

  Here, i >> 1 is equivalent to dividing i by 2, and i & 1 checks if i is odd (1) or even (0).

Code

public class CountingBits {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        CountingBits cb = new CountingBits();
        int[] result1 = cb.countBits(2);
        for (int num : result1) {
            System.out.print(num + " ");
        }
        System.out.println();
        
        int[] result2 = cb.countBits(5);
        for (int num : result2) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

• Time complexity: O(n). We iterate through each number from 1 to n once.
• Space complexity: O(n). We use an array of size n+1 to store the results.

This solution is efficient and leverages the properties of binary numbers to count bits in linear time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?