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.

	#include<iostream>
	#include<cstdint>
	#include<math.h>
	using namespace std;
	int is_power_of_3(uint32_t n)
	{
	if (n == 1)
	return n;
	if (n % 3)
	return 0;
	return is_power_of_3(n / 3);
	}
	int is_power_of_3_with_prefined_number(uint32_t n)
	{
	uint32_t L = pow(3, 20);
	return (L%n)? 0: 1;
	}
	int main()
	{
	uint32_t n = pow(3,15);
	cout <<"input: "<< n << " is power of 3 O(log n/log 3): " << is_power_of_3(n) << endl;
	cout << "input: "<< n << " is power of 3 O(1) : " << is_power_of_3_with_prefined_number(n) << endl;
	return 1;
	}

view raw is_power_3.cpp hosted with ❤ by GitHub

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.

	# brute-force recursive division. O(N) were n is exponent in target = 3^N
	def is_power_of_3_recursive(target):
	if target == 1:
	return True
	if target % 3 != 0:
	return False
	return is_power_of_3_recursive(target//3)
	def faster_power_of_3(target):
	largest = 3**20
	return largest % target == 0
	input = 3**3*2
	print("recursive division ==> input = {} is_power_of_three = {}".format(input, is_power_of_3_recursive(input)))
	print("predefined number ==> input = {} is_power_of_three = {}".format(input, faster_power_of_3(input)))
	input = 3**6
	print("recursive division ==> input = {} is_power_of_three = {}".format(input, is_power_of_3_recursive(input)))
	print("predefined number ==> input = {} is_power_of_three = {}".format(input, faster_power_of_3(input)))
	input = 3**15 * 2
	print("recursive division ==> input = {} is_power_of_three = {}".format(input, is_power_of_3_recursive(input)))
	print("predefined number ==> input = {} is_power_of_three = {}".format(input, faster_power_of_3(input)))
	input = 3**20
	print("predefined number ==> input = {} is_power_of_three = {}".format(input, faster_power_of_3(input)))
	print("recursive division ==> input = {} is_power_of_three = {}".format(input, is_power_of_3_recursive(input)))

view raw is_power_of_3.py hosted with ❤ by GitHub

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.

	'''
	Write function to determine if given unsigned 32-bit number is a power of 3
	int is_power_of_3(uint32_t n)
	'''
	ceiling= 2**32 - 1
	def find_largest_powered_number(base, start, end, ceiling, last_found):
	if start > end:
	return last_found
	half = start + (end - start)//2
	candidate = base ** half
	if candidate > ceiling:
	return find_largest_powered_number(base, start, half -1, ceiling, last_found)
	else:
	last_found = candidate if candidate > last_found else last_found
	return find_largest_powered_number(base, half+1, end, ceiling, last_found)
	def is_power_of_n(target, base):
	max_value = find_largest_powered_number(base, 0, 32, ceiling, 0)
	return max_value % target == 0
	# test
	input=[3**10, 4*3**15, 3**8-1, 3**15]
	expected=[True, False, False, True]
	for i in range(len(input)):
	result = is_power_of_n(input[i], 3)
	print ("{} is power of 3 ?: {}".format(input[i], result))
	assert expected[i] == result

view raw is_power_of_3_2023.py hosted with ❤ by GitHub