How to check if an integer is a power of 3?

Algorithm Math

Algorithm Problem Overview

I saw this question, and pop up this idea.

Algorithm Solutions

Solution 1 - Algorithm

There exists a constant time (pretty fast) method for integers of limited size (e.g. 32-bit integers).

Note that for an integer N that is a power of 3 the following is true:

For any M <= N that is a power of 3, M divides N.
For any M <= N that is not a power 3, M does not divide N.

The biggest power of 3 that fits into 32 bits is 3486784401 (3^20). This gives the following code:

bool isPower3(std::uint32_t value) {
    return value != 0 && 3486784401u % value == 0;
}

Similarly for signed 32 bits it is 1162261467 (3^19):

bool isPower3(std::int32_t value) {
    return value > 0 && 1162261467 % value == 0;
}

In general the magic number is:

$3^{\lfloor log_3 {MAX} \rfloor}$ == pow(3, floor(log(MAX) / log(3)))

Careful with floating point rounding errors, use a math calculator like Wolfram Alpha to calculate the constant. For example for 2^63-1 (signed int64) both C++ and Java give 4052555153018976256, but the correct value is 4052555153018976267.

Solution 2 - Algorithm

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

Note that 1 is the zeroth power of three.

Edit: You also need to check for zero before the loop, as the loop will not terminate for n = 0 (thanks to Bruno Rothgiesser).

Solution 3 - Algorithm

I find myself slightly thinking that if by 'integer' you mean 'signed 32-bit integer', then (pseudocode)

return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467)

has a certain beautiful simplicity to it (the last number is 3^19, so there aren't an absurd number of cases). Even for an unsigned 64-bit integer there still be only 41 cases (thanks @Alexandru for pointing out my brain-slip). And of course would be impossible for arbitrary-precision arithmetic...

Solution 4 - Algorithm

I'm surprised at this. Everyone seems to have missed the fastest algorithm of all.

The following algorithm is faster on average - and dramatically faster in some cases - than a simple while(n%3==0) n/=3; loop:

bool IsPowerOfThree(uint n)
{
  // Optimizing lines to handle the most common cases extremely quickly
  if(n%3 != 0) return n==1;
  if(n%9 != 0) return n==3;

  // General algorithm - works for any uint
  uint r;
  n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;
}

The numeric constants in the code are 3^10, 3^5, and 3^3.

Performance calculations

In modern CPUs, DivRem is a often single instruction that takes a one cycle. On others it expands to a div followed by a mul and an add, which would takes more like three cycles altogether. Each step of the general algorithm looks long but it actually consists only of: DivRem, cmp, cmove, cmp, cand, cjmp, add. There is a lot of parallelism available, so on a typical two-way superscalar processor each step will likely execute in about 4 clock cycles, giving a guaranteed worst-case execution time of about 25 clock cycles.

If input values are evenly distributed over the range of UInt32, here are the probabilities associated with this algorithm:

Return in or before the first optimizing line: 66% of the time
Return in or before the second optimizing line: 89% of the time
Return in or before the first general algorithm step: 99.998% of the time
Return in or before the second general algorithm step: 99.99998% of the time
Return in or before the third general algorithm step: 99.999997% of the time

This algorithm outperforms the simple while(n%3==0) n/=3 loop, which has the following probabilities:

Return in the first iteration: 66% of the time
Return in the first two iterations: 89% of the time
Return in the first three iterations: 97% of the time
Return in the first four iterations: 98.8% of the time
Return in the first five iterations: 99.6% of the time ... and so on to ...
Return in the first twelve iterations: 99.9998% of the time ... and beyond ...

What is perhaps even more important, this algorithm handles midsize and large powers of three (and multiples thereof) much more efficiently: In the worst case the simple algorithm will consume over 100 CPU cycles because it will loop 20 times (41 times for 64 bits). The algorithm I present here will never take more than about 25 cycles.

Extending to 64 bits

Extending the above algorithm to 64 bits is trivial - just add one more step. Here is a 64 bit version of the above algorithm optimized for processors without efficient 64 bit division:

bool IsPowerOfThree(ulong nL)
{
  // General algorithm only
  ulong rL;
  nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
  nL = Math.DivRem(nL+rL,   59049, out rL); if(nL!=0 && rL!=0) return false;
  uint n = (uint)nL + (uint)rL;
  n = Math.DivRem(n,   243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;

}

The new constant is 3^20. The optimization lines are omitted from the top of the method because under our assumption that 64 bit division is slow, they would actually slow things down.

Why this technique works

Say I want to know if "100000000000000000" is a power of 10. I might follow these steps:

I divide by 10^10 and get a quotient of 10000000 and a remainder of 0. These add to 10000000.
I divide by 10^5 and get a quotient of 100 and a remainder of 0. These add to 100.
I divide by 10^3 and get a quotient of 0 and a remainderof 100. These add to 100.
I divide by 10^2 and get a quotient of 1 and a remainder of 0. These add to 1.

Because I started with a power of 10, every time I divided by a power of 10 I ended up with either a zero quotient or a zero remainder. Had I started out with anything except a power of 10 I would have sooner or later ended up with a nonzero quotient or remainder.

In this example I selected exponents of 10, 5, and 3 to match the code provided previously, and added 2 just for the heck of it. Other exponents would also work: There is a simple algorithm for selecting the ideal exponents given your maximum input value and the maximum power of 10 allowed in the output, but this margin does not have enough room to contain it.

NOTE: You may have been thinking in base ten throughout this explanation, but the entire explanation above can be read and understood identically if you're thinking in in base three, except the exponents would have been expressed differently (instead of "10", "5", "3" and "2" I would have to say "101", "12", "10" and "2").

Solution 5 - Algorithm

This is a summary of all good answers below this questions, and the performance figures can be found from the LeetCode article.

1. Loop Iteration

Time complexity O(log(n)), space complexity O(1)

public boolean isPowerOfThree(int n) {
    if (n < 1) {
        return false;
    }

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

    return n == 1;
}

2. Base Conversion

Convert the integer to a base 3 number, and check if it is written as a leading 1 followed by all 0. It is inspired by the solution to check if a number is power of 2 by doing n & (n - 1) == 0

Time complexity: O(log(n)) depending on language and compiler, space complexity: O(log(n))

public boolean isPowerOfThree(int n) {
    return Integer.toString(n, 3).matches("^10*$");
}

3. Mathematics

If n = 3^i, then i = log(n) / log(3), and thus comes to the solution

Time complexity: depending on language and compiler, space complexity: O(1)

public boolean isPowerOfThree(int n) {
    return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
}

4. Integer Limitations

Because 3^19 = 1162261467 is the largest power of 3 number fits in a 32 bit integer, thus we can do

Time complexity: O(1), space complexity: O(1)

public boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

5. Integer Limitations with Set

The idea is similar to #4 but use a set to store all possible power of 3 numbers (from 3^0 to 3^19). It makes code more readable.

6. Recursive (C++11)

This solution is specific to C++11, using template meta programming so that complier will replace the call isPowerOf3<Your Input>::cValue with calculated result.

Time complexity: O(1), space complexity: O(1)

template<int N>
struct isPowerOf3 {
    static const bool cValue = (N % 3 == 0) && isPowerOf3<N / 3>::cValue;
};

template<>
struct isPowerOf3<0> {
    static const bool cValue = false;
};

template<>
struct isPowerOf3<1> {
    static const bool cValue = true;
};

int main() {
    cout<<isPowerOf3<1162261467>::cValue;
    return 0;
}

Solution 6 - Algorithm

if (log n) / (log 3) is integral then n is a power of 3.

Solution 7 - Algorithm

Recursively divide by 3, check that the remainder is zero and re-apply to the quotient.

Note that 1 is a valid answer as 3 to the zero power is 1 is an edge case to beware.

Solution 8 - Algorithm

Very interesting question, I like the answer from starblue, and this is a variation of his algorithm which will converge little bit faster to the solution:

private bool IsPow3(int n)
{
    if (n == 0) return false;
    while (n % 9 == 0)
    {
        n /= 9;
    }
    return (n == 1 || n == 3);
}

Solution 9 - Algorithm

Between powers of two there is at most one power of three. So the following is a fast test:

Find the binary logarithm of n by finding the position of the leading 1 bit in the number. This is very fast, as modern processors have a special instruction for that. (Otherwise you can do it by bit twiddling, see http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog">Bit Twiddling Hacks).
Look up the potential power of three in a table indexed by this position and compare to n (if there is no power of three you can store any number with a different binary logarithm).
If they are equal return yes, otherwise no.

The runtime depends mostly on the time needed for accessing the table entry. If we are using machine integers the table is small, and probably in cache (we are using it many millions of times, otherwise this level of optimization wouldn't make sense).

Solution 10 - Algorithm

Here is a nice and fast implementation of Ray Burns' method in C:

bool is_power_of_3(unsigned x) {
    if (x > 0x0000ffff)
        x *= 0xb0cd1d99;	// multiplicative inverse of 59049
    if (x > 0x000000ff)
        x *= 0xd2b3183b;	// multiplicative inverse of 243
    return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

It uses the multiplicative inverse trick for to first divide by 3^10 and then by 3^5. Finally, it needs to check whether the result is 1, 3, 9, 27, 81, or 243, which is done by some simple hashing that I found by trial-and-error.

On my CPU (Intel Sandy Bridge), it is quite fast, but not as fast as the method of starblue that uses the binary logarithm (which is implemented in hardware on that CPU). But on a CPU without such an instruction, or when lookup tables are undesirable, it might be an alternative.

Solution 11 - Algorithm

How large is your input? With O(log(N)) memory you can do faster, O(log(log(N)). Precompute the powers of 3 and then do a binary search on the precomputed values.

Solution 12 - Algorithm

Simple and constant-time solution:

return n == power(3, round(log(n) / log(3)))

Solution 13 - Algorithm

For really large numbers n, you can use the following math trick to speed up the operation of

  n % 3 == 0

which is really slow and most likely the choke point of any algorithm that relies on repeated checking of remainders. You have to understand modular arithmetic to follow what I am doing, which is part of elementary number theory.

Let x = Σ _k a _k 2 ^k be the number of interest. We can let the upper bound of the sum be ∞ with the understanding that a _k = 0 for some k > M. Then

0 ≡ x ≡ Σ _k a _k 2 ^k ≡ Σ _k a _2k 2 ^2k + a _2k+1 2 ^2k+1 ≡ Σ _k 2 ^2k ( a _2k + a _2k+1 2) ≡ Σ _k a _2k + a _2k+1 2 (mod 3)

since 2^2k ≡ 4 ^k ≡ 1^k ≡ 1 (mod 3).

Given a binary representation of a number x with 2n+1 bits as

x₀ x₁ x₂ ... x_2n+1

where x_k ∈{0,1} you can group odd even pairs

(x₀ x₁) (x₂ x₃) ... (x_2n x_2n+1).

Let q denote the number of pairings of the form (1 0) and let r denote the number of pairings of the form (0 1). Then it follows from the equation above that 3 | x if and only if 3 | (q + 2r). Furthermore, you can show that 3|(q + 2r) if and only if q and r have the same remainder when divided by 3.

So an algorithm for determining whether a number is divisible by 3 could be done as follows

 q = 0, r = 0
 for i in {0,1, .., n}
     pair <- (x_{2i} x_{2i+1})
     if pair == (1 0)
         switch(q)
             case 0:
                 q = 1;
                 break;
             case 1:
                 q = 2;
                 break;
             case 2:
                 q = 0;
                 break;
     else if pair == (0 1)
         switch(r)
             case 0:
                 r = 1;
                 break;
             case 1:
                 r = 2;
                 break;
             case 2:
                 r = 0;
 return q == r

This algorithm is more efficient than the use of %.

--- Edit many years later ----

I took a few minutes to implement a rudimentary version of this in python that checks its true for all numbers up to 10^4. I include it below for reference. Obviously, to make use of this one would implement this as close to hardware as possible. This scanning technique can be extended to any number that one wants to by altering the derivation. I also conjecture the 'scanning' portion of the algorithm can be reformulated in a recursive O(log n) type formulation similar to a FFT, but I'd have to think on it.

#!/usr/bin/python

def bits2num(bits):
    num = 0
    for i,b in enumerate(bits):
        num += int(b) << i
    return num

def num2bits(num):
    base = 0
    bits = list()
    while True:
        op = 1 << base
        if op > num:
            break
        bits.append(op&num !=0)
        base += 1
    return "".join(map(str,map(int,bits)))[::-1]

def div3(bits):

    n = len(bits)

    if n % 2 != 0:
        bits = bits + '0'

    n = len(bits)

    assert n % 2 == 0

    q = 0
    r = 0
    for i in range(n/2):
        pair = bits[2*i:2*i+2]
        if pair == '10':
            if q == 0:
                q = 1
            elif q == 1:
                q = 2
            elif q == 2:
                q = 0
        elif pair == '01':
            if r == 0:
                r = 1
            elif r == 1:
                r = 2
            elif r == 2:
                r = 0
        else:
            pass

    return q == r

for i in range(10000):
    truth = (i % 3)  == 0
    bits = num2bits(i)
    check  = div3(bits)
    assert truth == check

Solution 14 - Algorithm

You can do better than repeated division, which takes O(lg(X) * |division|) time. Essentially you do a binary search on powers of 3. Really we will be doing a binary search on N, where 3^N = input value). Setting the Pth binary digit of N corresponds to multiplying by 3^(2^P), and values of the form 3^(2^P) can be computed by repeated squaring.

Algorithm

Let the input value be X.
Generate a list L of repeated squared values which ends once you pass X.
Let your candidate value be T, initialized to 1.
For each E in reversed L, if T*E <= X then let T *= E.
Return T == X.

Complexity:

O(lg(lg(X)) * |multiplication|)

Generating and iterating over L takes lg(lg(X)) iterations, and multiplication is the most expensive operation in an iteration.

Solution 15 - Algorithm

The fastest solution is either testing if n > 0 && 3**19 % n == 0 as given in another answer or perfect hashing (below). First I'm giving two multiplication-based solutions.

Multiplication

I wonder why everybody missed that multiplication is much faster than division:

for (int i=0, pow=1; i<=19, pow*=3; ++i) {
    if (pow >= n) {
        return pow == n;
    }
}
return false;

Just try all powers, stop when it grew too big. Avoid overflow as 3**19 = 0x4546B3DB is the biggest power fitting in signed 32-bit int.

Multiplication with binary search

Binary search could look like

int pow = 1;
int next = pow * 6561; // 3**8
if (n >= next) pow = next;
next = pow * 81; // 3**4
if (n >= next) pow = next;
next = pow * 81; // 3**4; REPEATED
if (n >= next) pow = next;
next = pow * 9; // 3**2
if (n >= next) pow = next;
next = pow * 3; // 3**1
if (n >= next) pow = next;
return pow == next;

One step is repeated, so that the maximum exponent 19 = 8+4+4+2+1 can exactly be reached.

Perfect hashing

There are 20 powers of three fitting into a signed 32-bit int, so we take a table of 32 elements. With some experimentation, I found the perfect hash function

def hash(x):
    return (x ^ (x>>1) ^ (x>>2)) & 31;

mapping each power to a distinct index between 0 and 31. The remaining stuff is trivial:

// Create a table and fill it with some power of three.
table = [1 for i in range(32)]
// Fill the buckets.
for n in range(20): table[hash(3**n)] = 3**n;

Now we have

table = [     1162261467, 1, 3, 729, 14348907, 1, 1, 1,     1, 1, 19683, 1, 2187, 81, 1594323, 9,     27, 43046721, 129140163, 1, 1, 531441, 243, 59049,     177147, 6561, 1, 4782969, 1, 1, 1, 387420489]

and can test very fast via

def isPowerOfThree(x):
    return table[hash(x)] == x

Solution 16 - Algorithm

Your question is fairly easy to answer by defining a simple function to run the check for you. The example implementation shown below is written in Python but should not be difficult to rewrite in other languages if needed. Unlike the last version of this answer, the code shown below is far more reliable.

Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> import math
>>> def power_of(number, base):
	return number == base ** round(math.log(number, base))

>>> base = 3
>>> for power in range(21):
	number = base ** power
	print(f'{number} is '
	      f'{"" if power_of(number, base) else "not "}'
	      f'a power of {base}.')
	number += 1
	print(f'{number} is '
	      f'{"" if power_of(number, base) else "not "}'
	      f'a power of {base}.')
	print()

	
1 is a power of 3.
2 is not a power of 3.

3 is a power of 3.
4 is not a power of 3.

9 is a power of 3.
10 is not a power of 3.

27 is a power of 3.
28 is not a power of 3.

81 is a power of 3.
82 is not a power of 3.

243 is a power of 3.
244 is not a power of 3.

729 is a power of 3.
730 is not a power of 3.

2187 is a power of 3.
2188 is not a power of 3.

6561 is a power of 3.
6562 is not a power of 3.

19683 is a power of 3.
19684 is not a power of 3.

59049 is a power of 3.
59050 is not a power of 3.

177147 is a power of 3.
177148 is not a power of 3.

531441 is a power of 3.
531442 is not a power of 3.

1594323 is a power of 3.
1594324 is not a power of 3.

4782969 is a power of 3.
4782970 is not a power of 3.

14348907 is a power of 3.
14348908 is not a power of 3.

43046721 is a power of 3.
43046722 is not a power of 3.

129140163 is a power of 3.
129140164 is not a power of 3.

387420489 is a power of 3.
387420490 is not a power of 3.

1162261467 is a power of 3.
1162261468 is not a power of 3.

3486784401 is a power of 3.
3486784402 is not a power of 3.

>>>

NOTE: The last revision has caused this answer to become nearly the same as TMS' answer.

Solution 17 - Algorithm

Set based solution...

DECLARE @LastExponent smallint, @SearchCase decimal(38,0)

SELECT
    @LastExponent = 79, -- 38 for bigint
    @SearchCase = 729

;WITH CTE AS
(
    SELECT
        POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result,
        ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent
    FROM
        sys.columns c1, sys.columns c2
)
SELECT
    Result, Exponent
FROM
    CTE
WHERE
    Exponent <= @LastExponent
    AND
    Result = @SearchCase

With SET STATISTICS TIME ON it record the lowest possible, 1 millisecond.

Solution 18 - Algorithm

Another approach is to generate a table on compile time. The good thing is, that you can extend this to powers of 4, 5, 6, 7, whatever

template<std::size_t... Is>
struct seq
{  };

template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>
{  };

template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>
{  };

template<std::size_t N>
struct PowersOfThreeTable
{
    std::size_t indexes[N];
    std::size_t values[N];

    static constexpr std::size_t size = N;
};

template<typename LambdaType, std::size_t... Is>
constexpr PowersOfThreeTable<sizeof...(Is)>
    generatePowersOfThreeTable(seq<Is...>, LambdaType evalFunc)
{
    return { {Is...}, {evalFunc(Is)...} };
}

template<std::size_t N, typename LambdaType>
constexpr PowersOfThreeTable<N> generatePowersOfThreeTable(LambdaType evalFunc)
{
    return generatePowersOfThreeTable(gen_seq<N>(), evalFunc);
}

template<std::size_t Base, std::size_t Exp>
struct Pow
{
    static constexpr std::size_t val = Base * Pow<Base, Exp-1ULL>::val;
};

template<std::size_t Base>
struct Pow<Base, 0ULL>
{
    static constexpr std::size_t val = 1ULL;
};

template<std::size_t Base>
struct Pow<Base, 1ULL>
{
    static constexpr std::size_t val = Base;
};

constexpr std::size_t tableFiller(std::size_t val)
{ 
    return Pow<3ULL, val>::val;
}

bool isPowerOfThree(std::size_t N)
{
    static constexpr unsigned tableSize = 41; //choosen by fair dice roll

    static constexpr PowersOfThreeTable<tableSize> table = 
            generatePowersOfThreeTable<tableSize>(tableFiller);
    
    for(auto a : table.values)
        if(a == N)
            return true;
    return false;
}

Solution 19 - Algorithm

I measured times (C#, Platform target x64) for some solutions.

using System;
class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (uint n = ~0u; n > 0; n--) ;
        Console.WriteLine(sw.Elapsed);              // nada   1.1 s
        sw.Restart();
        for (uint n = ~0u; n > 0; n--) isPow3a(n);
        Console.WriteLine(sw.Elapsed);              // 3^20  17.3 s
        sw.Restart();
        for (uint n = ~0u; n > 0; n--) isPow3b(n);
        Console.WriteLine(sw.Elapsed);              // % /   10.6 s
        Console.Read();
    }

    static bool isPow3a(uint n)  // Elric
    {
        return n > 0 && 3486784401 % n == 0;
    }

    static bool isPow3b(uint n)  // starblue
    {
        if (n > 0) while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

Another way (of splitting hairs).

using System;
class Program
{
    static void Main()
    {
        Random rand = new Random(0); uint[] r = new uint[512];
        for (int i = 0; i < 512; i++)
            r[i] = (uint)(rand.Next(1 << 30)) << 2 | (uint)(rand.Next(4));
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) ;
        Console.WriteLine(sw.Elapsed);                    //   0.3 s
        sw.Restart();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) isPow3c(r[j]);
        Console.WriteLine(sw.Elapsed);                    //  10.6 s
        sw.Restart();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) isPow3b(r[j]);
        Console.WriteLine(sw.Elapsed);                    //   9.0 s
        Console.Read();
    }

    static bool isPow3c(uint n)
    { return (n & 1) > 0 && 3486784401 % n == 0; }

    static bool isPow3b(uint n)
    { if (n > 0) while (n % 3 == 0) n /= 3; return n == 1; }
}

Solution 20 - Algorithm

Python program to check whether the number is a POWER of 3 or not.

    def power(Num1):
        while Num1 % 3 == 0:
            Num1 /= 3
        return Num1 == 1


    Num1 = int(input("Enter a Number: "))
    print(power(Num1))

Solution 21 - Algorithm

Python solution

from math import floor
from math import log

def IsPowerOf3(number):
  p = int(floor(log(number) / log(3)))
  power_floor = pow(3, p)
  power_ceil = power_floor * 3
  if power_floor == number or power_ceil == number:
    return True
  return False

This is much faster than the simple divide by 3 solution.

Proof: 3 ^ p = number

p log(3) = log(number) (taking log both side)

p = log(number) / log(3)

Solution 22 - Algorithm

Here's a general algorithm for finding out if a number is a power of another number:

bool IsPowerOf(int n,int b)
{
    if (n > 1)
    {
        while (n % b == 0)
        {
            n /= b;
        }
    }
    return n == 1;
}

Solution 23 - Algorithm

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main()
{
     int n, power=0;
      cout<<"enter a number"<<endl;
      cin>>n;
  if (n>0){
      
     for(int i=0; i<=n; i++)
     {
        
         int r=n%3;
      
            n=n/3;
         if (r==0){
            power++;
         }
            
         else{
               cout<<"not exactly power of 3";
                return 0;
           
             }
     }
    
   }

         cout<<"the power is "<<power<<endl;
  }

Solution 24 - Algorithm

This is a constant time method! Yes. O(1). For numbers of fixed length, say 32-bits.

Given that we need to check if an integer n is a power of 3, let us start thinking about this problem in terms of what information is already at hand.

1162261467 is the largest power of 3 that can fit into an Java int.
1162261467 = 3^19 + 0

The given n can be expressed as [(a power of 3) + (some x)]. I think it is fairly elementary to be able to prove that if x is 0(which happens iff n is a power of 3), 1162261467 % n = 0.

The general idea is that if X is some power of 3, X can be expressed as Y/3a, where a is some integer and X < Y. It follows the exact same principle for Y < X. The Y = X case is elementary.

So, to check if a given integer n is a power of three, check if n > 0 && 1162261467 % n == 0.

Solution 25 - Algorithm

Python:

return n > 0 and 1162261467 % n == 0

OR Calculate log:

lg = round(log(n,3))
return 3**lg == n

1st approach is faster than the second one.

Content Type	Original Author	Original Content on Stackoverflow
Question	Mask	View Question on Stackoverflow
Solution 1 - Algorithm	Elric	View Answer on Stackoverflow
Solution 2 - Algorithm	starblue	View Answer on Stackoverflow
Solution 3 - Algorithm	AakashM	View Answer on Stackoverflow
Solution 4 - Algorithm	Ray Burns	View Answer on Stackoverflow
Solution 5 - Algorithm	HaoCS	View Answer on Stackoverflow
Solution 6 - Algorithm	PaulJWilliams	View Answer on Stackoverflow
Solution 7 - Algorithm	JB King	View Answer on Stackoverflow
Solution 8 - Algorithm	user218447	View Answer on Stackoverflow
Solution 9 - Algorithm	starblue	View Answer on Stackoverflow
Solution 10 - Algorithm	Falk Hüffner	View Answer on Stackoverflow
Solution 11 - Algorithm	Alexandru	View Answer on Stackoverflow
Solution 12 - Algorithm	Tomas	View Answer on Stackoverflow
Solution 13 - Algorithm	ldog	View Answer on Stackoverflow
Solution 14 - Algorithm	Craig Gidney	View Answer on Stackoverflow
Solution 15 - Algorithm	maaartinus	View Answer on Stackoverflow
Solution 16 - Algorithm	Noctis Skytower	View Answer on Stackoverflow
Solution 17 - Algorithm	gbn	View Answer on Stackoverflow
Solution 18 - Algorithm	NaCl	View Answer on Stackoverflow
Solution 19 - Algorithm	P_P	View Answer on Stackoverflow
Solution 20 - Algorithm	SATYAM TRIPATHI	View Answer on Stackoverflow
Solution 21 - Algorithm	ankurchauhan21	View Answer on Stackoverflow
Solution 22 - Algorithm	Hengameh	View Answer on Stackoverflow
Solution 23 - Algorithm	6ZUN9	View Answer on Stackoverflow
Solution 24 - Algorithm	Debosmit Ray	View Answer on Stackoverflow
Solution 25 - Algorithm	Archit Pandey	View Answer on Stackoverflow