Power of Three

Easy

0/40

Average time to solve is 15m

Contributed by

6 upvotes

Asked in companies

Problem statement

Given an integer 'N', you need to determine whether the given integer is a power of 3 or not.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases.

The first and the only line of each test case contains the integer ‘N’ denoting the number.

Output Format:

For each test case, on a separate line, output one integer 0 or 1. Print 1, if N is a power of 3, or 0 otherwise.

Print the output of each test case in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^9

Time limit: 1 sec

Sample Input 1:

2
81
6

Sample Output 1:

1
0

Explanation Of Sample Input 1:

For the first test case, 81 = 3^4. So, return 1.
For the second test case, 6 = 2 * 3^1. So, return 0.

Sample Input 2:

2
27
1

Sample Output 2:

1
1

Explanation Of Sample Input 2:

For the first test case, 27 = 3^3. So, return 1.
For the second test case, 1 =  3^0. So, return 1.

Hint 1

Use basic maths.

Approaches (1)

Approach 1

Greedy Approach

Approach: The idea here is to keep dividing ‘N’ by 3 every time till ‘N’ is divisible by 3. If at the end N is greater than 1 then the number will not be divisible by 3.

The algorithm is as follows :

Declare a while loop with condition that ‘N’ % 3 == 0.
- Divide ‘N’ by 3, ‘N’ = ‘N’ / 3.
If ‘N’ > 1, return 0 because the given integer is not a power of three.
Otherwise, return 1.

Time Complexity

O(logN), where N is the given number.

Here we are dividing N every time by 3, which is of the order logN base 3. So, the overall time complexity is O(logN).

Space Complexity

O(1),

As are using constant extra space.

(100% EXP penalty)

Power of Three

Console