Calculating the Power of the Fantastic Four - codepath/compsci_guides GitHub Wiki

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

Problem 5: Calculating the Power of the Fantastic Four

The superhero team, The Fantastic Four, are training to increase their power levels. Their power level is represented as a power of 4. Write a recursive function that calculates the power of 4 raised to the nth power to determine their training level.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 mins
  • 🛠️ Topics: Recursion, Exponentiation

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?
  • Q: What is the main task in this problem?
    • A: The task is to calculate 4 raised to the power of n using a recursive function.
  • Q: Does the input n only include positive integers?
    • A: No, n can be positive, zero, or negative.
HAPPY CASE
Input: 2
Output: 16
Explanation: 4 raised to the power of 2 (4 * 4) is 16.

Input: -2
Output: 0.0625
Explanation: 4 raised to the power of -2 is 1/(4 * 4) = 0.0625.

EDGE CASE
Input: 0
Output: 1
Explanation: 4 raised to the power of 0 is 1 (by definition of any number raised to the power of 0).

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 Recursive Exponentiation Problems, we want to consider the following approaches:

  • Recursive Calculation: Multiply 4 by the result of the function called with n-1 for positive n. For negative n, multiply 1/4 by the result of the function called with -n-1.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Use recursion to calculate 4 raised to the power of n. For positive n, recursively multiply by 4. For negative n, recursively multiply by 1/4.

Recursive Approach:

1) Base case: If `n` is 0, return 1 (since any number raised to the power of 0 is 1).
2) If `n` is positive, return 4 times the result of the function called with `n - 1`.
3) If `n` is negative, return 1 divided by 4 times the result of the function called with `-n - 1`.

⚠️ Common Mistakes

  • Forgetting to handle negative exponents correctly, which should involve calculating the reciprocal.
  • Not defining the base case properly, leading to infinite recursion.

4: I-mplement

Implement the code to solve the algorithm.

def power_of_four(n):
    if n == 0:
        return 1
    elif n > 0:
        return 4 * power_of_four(n - 1)
    else:
        return 1 / (4 * power_of_four(-n - 1))

5: R-eview

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

  • Trace through the power_of_four function with the input 2. The function should return 16 after two recursive calls.
  • Trace through the function with the input -2. The function should return 0.0625 after two recursive calls.

6: E-valuate

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

  • Time Complexity: O(N) where N is the absolute value of the input n. The function makes one recursive call per unit decrease in n, leading to linear time complexity.
  • Space Complexity: O(N) due to the recursion stack. The depth of recursion is proportional to the absolute value of n, leading to linear space usage.