DSA SheetEasy
EditorialPractice

RECURSION & BACKTRACKING › RECURSION PROBLEMS

Power of Three

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 26

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionwhy repeated division tests the definition directly

The nonnegative powers of three are 1, 3, 9, 27, and so on. Every one of them can be divided by 3 repeatedly until it reaches 1. Any positive integer with another prime factor, or with a leftover factor after the divisions stop, cannot be in that sequence.

Start by rejecting n <= 0, because powers of three in this problem begin at 3^0 = 1. For a positive n, keep dividing while 3 divides it. A valid power leaves exactly 1; every other positive input leaves a value greater than 1. The loop therefore checks both divisibility and the final value without storing any powers.

Approach

  1. Reject n < 1, because zero and negative integers are not powers of three in the required integer sequence, and zero would otherwise remain zero forever when divided by 3.
  2. While n is divisible by 3, divide it by 3. Each division removes one factor of 3 without changing whether the original number belongs to the sequence.
  3. Return whether the remaining value is 1. A remainder of 1 means the input was entirely made of factors of 3; any other remainder contains an extra factor.
  4. Use integer division only after the modulo check, so every division is exact and no fractional intermediate value can hide a non-power.

Complexity

MEASUREBOUNDWHY
TimeO(log_3 n)Each loop iteration divides the current value by 3, so after t iterations its size has fallen by a factor of 3^t. No value is processed more than once, and at most logarithmically many divisions fit before reaching 1.
SpaceO(1) extraThe algorithm stores only the input and a constant number of local values; no working structure grows with n. The returned boolean is required output and is excluded from extra space, so the bound stays O(1) even for the largest valid input.
Here log_3 n means the logarithm of n with base 3.

Annotated solutionC++ · iterative division · the direct definition in code

CPPRepeatedly remove factors of 3, then check that nothing remains except 1.
#include <vector>
using namespace std;

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n < 1) return false;

        while (n % 3 == 0) {
            n /= 3;
        }

        return n == 1;
    }
};

The guard must come before the loop. In particular, n = 0 satisfies 0 % 3 == 0 and 0 / 3 is still 0, so a loop without the guard never terminates for that input. Once positivity is established, every loop iteration strictly reduces n, making termination immediate.

The maximum-power alternativea constant-time divisibility test when the integer range is fixed

The largest power of three that fits in a signed 32-bit int is 3^19 = 1162261467; the next power, 3^20, is larger than the maximum positive int. Every positive power of three in the allowed range divides this largest power exactly, while a positive non-power cannot divide it. That gives a one-check alternative.

CPPCheck whether the positive input divides the largest power of three that fits in int.
#include <vector>
using namespace std;

class Solution {
public:
    bool isPowerOfThree(int n) {
        const int largestPower = 1162261467;
        return n > 0 && largestPower % n == 0;
    }
};

This version is an optimisation for the fixed 32-bit range, not a generally reusable mathematical test. It runs in O(1) time and O(1) extra space, but the constant is tied to the integer type: changing the range requires recomputing the largest safe power. The loop version is clearer and adapts naturally when the numeric range changes.

Common mistakestwo wrong code shapes that survive simple tests

Previous · Power of Two