Power of 3 problem

Problem

Write function to determine if given unsigned 32-bit number is a power of 3

    int is_power_of_3(uint32_t n)

First of all, I took this as another algorithm question and tried to find out how I can solve this problem in an algorithmic way. Thinking of whether there is any $O(N)$ way or $O(log N)$ way to solve this problem. That was the first mistake I made.

Failed but working approach:

The slowest way will be recursively dividing the target value, n until the remainder is 1.
This way will be really slow but not that slow. Since we will divide at most 20 times.

Then I thought I could find the faster way using binary search by setting the max value to n/3 but it was not the value but I used it as the exponent. It was not a good idea. This way was even worth.
If I can get the closest power of 3 number to the $n$, I could use that value for my binary search.

Any way, it was not the correct approach.

Event better way is just divide the largest power of 3 number by $n$ and see if there is any remainder. It works because if $n$ is a power of 3 number, it should be one of multiples consisting of the largest number.


Here is the complete code.



Practice statistics

04:13: to come up with the brute-force approach

06:07: to come up with the other approaches

12:22: to look up the largest power of 3 numbers for 32 bits

          and write up the hybrid approach.

Minor misuse of ^ and inclusion of "cstdint> was added.


UPDATE(2019-07-22): solve this problem again but made mistake to use the binary search in a wrong way and wrote the code slower than brute-force recursive division. 

Here is the python solution for both brute-force and predefined value way.


Practice statistics
29:00 : to write up the working but slowest binary search approach.

UPDATE(2023-01-29): solved again with python. Expended the concept to power of N.