Unit 7 Session 1 (Click for link to problem statements)
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?
n = 0
or negative values?
n = 0
, return True
(since (1 = 4^0)), and for negative values, return False
as they cannot be powers of a positive number.HAPPY CASE
Input: 16
Output: True
Explanation: 16 is a power of four (\(16 = 4^2\)).
EDGE CASE
Input: 0
Output: True
Explanation: 0 can be considered as \(4^0 = 1\) (not zero, correct to \(1 = 4^0\)).
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.
This is a straightforward recursive problem where the strategy is:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Implement a recursive function that checks if a number can be divided by four without leaving a remainder until it is reduced to 1.
1) Base Case 1: If `n` is 1, return True (since \(1 = 4^0\)).
2) Base Case 2: If `n` is less than 1 or if `n` modulo 4 is not zero, return False.
3) Recursive Case: Return a recursive call with `n` divided by 4.
⚠️ Common Mistakes
n = 0
and negative numbers.Implement the code to solve the algorithm.
def is_power_of_four(n):
if n == 1:
return True
if n < 1 or n % 4 != 0:
return False
return is_power_of_four(n // 4)
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(log n)
in base 4, since we reduce n
by a factor of 4 with each recursive call.O(log n)
in base 4, due to the recursion stack size being proportional to how many times n
can be divided by 4.