We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Counting Bits

Number: 338

Difficulty: Easy

Paid? No

Companies: Microsoft, Google, Meta, Amazon, Adobe, Uber, Bloomberg, Nvidia

Problem Description

Given a non-negative integer n, return an array ans of length n + 1 such that for each index i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Key Insights

  • We can use dynamic programming to build the solution by utilizing the count of bits for smaller numbers.
  • The relationship dp[i] = dp[i >> 1] + (i & 1) holds, where i >> 1 gives the count for i divided by 2 (dropping the least significant bit) and (i & 1) checks if the least significant bit is 1.
  • This approach computes the result for each number in constant time, resulting in a linear time solution.

Space and Time Complexity

Time Complexity: O(n) Space Complexity: O(n)

Solution

We use a dynamic programming approach where an array (or list) dp is initialized with size n+1. The key idea is to iterate from 1 to n and for each number, use the formula dp[i] = dp[i >> 1] + (i & 1).

  • The expression (i >> 1) effectively divides i by 2, giving the count of 1's for that half number.
  • The (i & 1) operation checks if i is odd, adding 1 if true. This method ensures each dp[i] is computed in constant time, leading to an overall O(n) time complexity.

Code Solutions

def countBits(n):
    # Create a list to store the number of 1's for each number from 0 to n
    dp = [0] * (n + 1)
    # Loop over each number starting from 1, since dp[0] is already 0
    for i in range(1, n + 1):
        # dp[i] is computed as the count for i//2 plus 1 if i is odd (i & 1)
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

# Example usage:
# print(countBits(5)) -> [0, 1, 1, 2, 1, 2]
← Back to All Questions