Charizard's Battle Power Calculation - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25 mins
  • 🛠️ Topics: 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 calculate how many different ways Charizard can combine his moves to exactly match the target battle power by adding or subtracting the values of his moves.
  • Can Charizard add or subtract each move?
    • Yes, for each move, Charizard can either add or subtract its power.
HAPPY CASE
Input: 
    moves = [2, 2, 2], target = 2
Output: 
    3
Explanation:
    Charizard has three ways to reach the target power of 2:
    +2 +2 -2 = 2
    +2 -2 +2 = 2
    -2 +2 +2 = 2

EDGE CASE
Input: 
    moves = [1, 1], target = 0
Output: 
    2
Explanation:
    Charizard has two ways to reach a target power of 0:
    +1 -1 = 0
    -1 +1 = 0

2: M-atch

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

For Charizard's Battle Power Calculation, we want to consider the following approaches:

  • Dynamic Programming (DP): This is a variation of the ""Subset Sum"" problem, where we need to track the different sums that can be achieved by adding or subtracting elements.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use a dictionary (dp) to keep track of how many ways we can reach each sum of battle power as we process each move. For each move, we will update the current possible sums by either adding or subtracting the move's value to/from each previously reachable sum.

Steps:

  1. Initialization:

    • Start with a dictionary (dp) that initially has only one entry: dp[0] = 1, meaning that there is one way to reach a total of 0 (by doing nothing).

  2. Process Each Move:

    • For each move in the list of moves:
      • Create a new dictionary new_dp to store the updated sums.
      • For each sum in dp, calculate the two possible new sums by either adding or subtracting the current move, and update new_dp accordingly.

  3. Update the DP Table:

    • After processing each move, replace dp with new_dp.

  4. Return the Result:

    • After processing all moves, the dictionary dp will contain the number of ways to reach each sum. Return the count of ways to reach the target sum (dp[target]), or 0 if it is not in the dictionary.

4: I-mplement

Implement the code to solve the algorithm.

def charizard_battle_power(moves, target):
    # Dictionary to store number of ways to reach each sum
    dp = {0: 1}  # Initially, we can have 0 power in 1 way (by doing nothing)

    # Process each move
    for move in moves:
        new_dp = {}  # This will store updated sums for this move
        for current_sum, count in dp.items():
            # Add the move to the current sum
            new_dp[current_sum + move] = new_dp.get(current_sum + move, 0) + count
            # Subtract the move from the current sum
            new_dp[current_sum - move] = new_dp.get(current_sum - move, 0) + count
        
        dp = new_dp  # Move to the next move with updated possibilities

    # Return the number of ways to achieve the target sum
    return dp.get(target, 0)

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: moves = [2, 2, 2], target = 2
  • Expected Output: 3

Example 2:

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

6: E-valuate

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

Assume n is the number of moves and S is the sum of the move values.

  • Time Complexity: O(n * S), where n is the number of moves, and S is the range of possible sums (from -sum(moves) to sum(moves)).
  • Space Complexity: O(S) to store the dictionary with the possible sums.