# Two ways and O(1)

• solution 1:

``````return (n == 1 || n == 3 || n == 9 || n == 27 || n == 81 || n == 243 || n == 729 || n == 2187 || n == 6561 || n == 19683 || n == 59049 || n == 177147 || n == 531441 || n == 1594323 || n == 4782969 || n == 14348907 || n == 43046721 || n == 129140163 || n == 387420489 || n == 1162261467);
``````

I like this solution! very easy to understand!

solution 2:

``````return n>0?!(1162261467 % n):0;
``````

or:

``````return n>0?(1162261467 / n == 1162261467 / (double)n):0; //this is a little bit faster
``````

if a number is the power of 3, it must can be divided by 1162261467, which is the largest number who is the power of 3.

• Even if you list all powers of 3, you can speed it up by doing a binary search because they are sorted :)

• Could be even faster by using a hashmap

• I think the solution 2 is not general because for a power of 4 or 6, it doesn't work.

• Yeah, It only works for prime numbers~

• yeah, just as jedihy said, hashmap or hashtable works even better~

• The overhead of setting up and populating the hashtable will definitely make it slower. I can almost bet 2 cents that an efficient binary search over an array [ O(n) ] will even defeat the hashtable [ O(1) ] in this scenario. Please don't say I'm wrong if you don't show benchmarks. Wait, is this sarcasm?

• You can preprocess the hash table and save it in a class variable. Then when you query you do not need to redo the setting up.

It will be faster than doing binary search at every query.
Don't you think so?

• That means you're relying on an implementation detail on LeetCode's systems. You don't know how the context of their tests are setup. Are they reloading the class in a sandbox for every test case? Are they using a single glass and making new instances for every test case? Do they make a single instance and just fire method calls with parameters for each test case? Are they pooling instances and firing testcases in parallel? I feel these things will affect the performance of such approach. What do you feel?

• Unless they reload the class for every test case, the class variable should set up once and shared between instances isn't it?

In a real life, preprocess a hash table and store in a class variable is commonly used. But again, in real life I will write solution 2.

• why is

``````return n>0?(1162261467 / n == 1162261467 / (double)n):0;
``````

faster?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.