The problem
Decide whether n is a power of four.
Input: 64 Output: true
Picture it
Picture the switch panel again: exactly one switch on, and it must sit at an even position (1, 4, 16, 64…). A mask of every even position checks that.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Power of two and n & 0x55555555 ≠ 0. O(1).
Python solution
def is_power_of_four(n):
return n > 0 and n & (n - 1) == 0 and n & 0x55555555 != 0In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.