Two ways and O(1)


  • 22
    W

    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.


  • 1
    E

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


  • 0

    Could be even faster by using a hashmap


  • 0

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


  • 0
    W

    Yeah, It only works for prime numbers~


  • 0
    W

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


  • 0
    O

    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?


  • 0

    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?


  • 0
    O

    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?


  • 0

    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.


  • 1
    D

    why is

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

    faster?


Log in to reply
 

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