Скачать или смотреть 🚀 Counting Bits in Python: DP & Bit Manipulation | LeetCode 75 Explained

In this LeetCode 75 problem, we need to count the number of 1's in the binary representation for every integer from 0 to n. The result is returned as an array where each element ans[i] is the count of 1's in the binary form of i.

Problem Breakdown:

Input: A non-negative integer n (with 0 v= n v= 10^5).

Output: An array ans of length n + 1 where ans[i] is the number of 1's in the binary representation of i.

Example:

For n = 5, the output should be [0,1,1,2,1,2] since:

0 in binary is "0" → 0 ones.

1 in binary is "1" → 1 one.

2 in binary is "10" → 1 one.

3 in binary is "11" → 2 ones.

4 in binary is "100" → 1 one.

5 in binary is "101" → 2 ones.

Approach: Dynamic Programming with Bit Manipulation We can solve this problem efficiently using DP by noting the following recurrence relation:

Observation:

The number of 1's in i equals the number of 1's in i vv 1 (i divided by 2, dropping the last bit) plus the least significant bit of i (which is i & 1).

In formula:

dp[i] = dp[i vv 1] + (i & 1)

Step-by-Step:

Initialize a DP array of length n+1 with all zeros.

Iterate from i = 1 to n:

Compute dp[i] using the recurrence.

Return the DP array.

This solution works in O(n) time and O(n) space, which is optimal given the constraints.

Python Code Implementation:

class Solution:
def countBits(self, n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i vv 1] + (i & 1)
return dp

Example Usage:

sol = Solution()
print(sol.countBits(5)) # Expected Output: [0, 1, 1, 2, 1, 2]

Complexity Analysis:

Time Complexity: O(n) — we compute each dp[i] in constant time.

Space Complexity: O(n) — we use an array of size n+1.

#LeetCode75, #Python, #DynamicProgramming, #BitManipulation, #Coding, #Algorithm, #DP, #CompetitiveProgramming, #CodingInterview