Power of Three - Practice Coding Problems

Power of Three - Problem

Math Recursion Easy

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3^x.

Input & Output

Example 1 — Perfect Power of Three

$ Input: n = 27

› Output: true

💡 Note: 27 = 3³, so it is a power of three

Example 2 — Not a Power of Three

$ Input: n = 0

› Output: false

💡 Note: 0 is not a power of three (powers of 3 are positive)

Example 3 — Base Case

$ Input: n = 1

› Output: true

💡 Note: 1 = 3⁰, so it is a power of three

Constraints

-2³¹ ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer n to check

Process

Apply mathematical test for power of 3

Output

Return true if n = 3^x for some integer x

Key Takeaway

🎯 Key Insight: Use mathematical properties like integer limitations or logarithms for efficient checking

Asked in

G Google 15 A Apple 8 M Microsoft 12

The key insight is recognizing that powers of 3 have special mathematical properties. The optimal approach uses the fact that 3^19 is the largest power of 3 in 32-bit range. Time: O(1), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Integer Limitation Method	O(1)	O(1)	Use the fact that 3^19 is the largest power of 3 in 32-bit range
Iterative Division	O(log n)	O(1)	Repeatedly divide by 3 until we can't divide evenly
Logarithm Method	O(1)	O(1)	Use mathematical logarithms to check if log₃(n) is an integer

Integer Limitation Method — Algorithm Steps

Handle edge case: n ≤ 0 returns false
Check if 1162261467 % n == 0
Return the boolean result

Visualization

Tap to expand

Step-by-Step Walkthrough

Maximum

3^19 = 1162261467 is largest power of 3 in range

Test

Check if max power of 3 is divisible by n

Result

If divisible, n must be a power of 3

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool solution(int n) {
    if (n <= 0) {
        return false;
    }
    
    // 3^19 = 1162261467 is the largest power of 3 in 32-bit range
    return 1162261467 % n == 0;
}

int main() {
    int n;
    scanf("%d", &n);
    
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Single modulo operation

✓ Linear Growth

Space Complexity

O(1)

No extra data structures used

✓ Linear Space

180.0K Views

Medium Frequency

~15 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Integer Limitation Method — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler