Counting Pikachu's Thunderbolt Charges - codepath/compsci_guides GitHub Wiki

Unit 12 Session 1 Standard (Click for link to problem statements)

Unit 12 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 20 mins
  • 🛠️ Topics: Bit manipulation, Dynamic Programming

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is the goal of the problem?
    • The goal is to return an array where each element represents the number of 1s (Thunderbolt charges) in the binary representation of each integer from 0 to n.
  • What is the maximum value of n?
    • The value of n can be as large as 10^5 based on typical constraints.
HAPPY CASE
Input: 
    n = 5
Output: 
    [0, 1, 1, 2, 1, 2]
Explanation:
    The number of Thunderbolt charges corresponds to the number of `1`s in the binary representation of numbers from 0 to 5.

EDGE CASE
Input: 
    n = 0
Output: 
    [0]
Explanation:
    When n = 0, the only value is `0`, and its binary representation contains `0` `1`s.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For counting the number of 1s in binary representations, we want to consider the following approaches:

  • Bit Manipulation: The number of 1s in a number’s binary representation can be computed efficiently using bit operations.
  • Dynamic Programming: We can use the results of previously computed numbers to compute the number of 1s for the next number based on its relationship to the previous numbers.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use dynamic programming to fill an array where each element represents the number of 1s in the binary representation of numbers from 0 to n. For each number i, if i is even, it has the same number of 1s as i // 2. If i is odd, it has one more 1 than i // 2.

Steps:

  1. Initialize an Array:

    • Create an array ans of length n + 1 initialized to zero.

  2. Iterate from 1 to n:

    • For each number i, compute the number of 1s using the relationship:
      • If i is even: ans[i] = ans[i // 2].
      • If i is odd: ans[i] = ans[i // 2] + 1.

  3. Return the Result:

    • Return the array ans.

4: I-mplement

Implement the code to solve the algorithm.

def thunderbolt_charges(n):
    # Initialize an array to store the number of 1's for each number from 0 to n
    ans = [0] * (n + 1)
    
    # For each number i, we use the relationship:
    # - If i is even, ans[i] = ans[i // 2] (same number of 1's as i//2)
    # - If i is odd, ans[i] = ans[i // 2] + 1 (same as i//2 but with an extra 1)
    for i in range(1, n + 1):
        if i % 2 == 0:
            ans[i] = ans[i // 2]  # Even case
        else:
            ans[i] = ans[i // 2] + 1  # Odd case (adds 1 extra 1-bit)
    
    return ans

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

  • Input: n = 5
  • Expected Output: [0, 1, 1, 2, 1, 2]

Example 2:

  • Input: n = 2
  • Expected Output: [0, 1, 1]

Example 3:

  • Input: n = 10
  • Expected Output: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the input value.

  • Time Complexity: O(n) because we compute the number of 1s for each integer from 0 to n.
  • Space Complexity: O(n) to store the result array ans.