Last Updated: 18 Apr, 2021

Birthday Gift

Moderate

Asked in company

Solve now

Problem statement

Ninja’s friend likes gifts very much. So on his birthday, Ninja wants to gift him a number ‘N’. He knows that his friend will like this number only if it is possible to represent 'N' as the distinct powers of ‘3’.

For example: 10 = 3 ^ 0 + 3 ^ 2.

Help Ninja to know whether his friend will like this number or not.

Input Format:

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

The first line of each test case contains a single integer ‘N’.

Output Format :

For each test case, return 1 if the number 'N' can be represented as the distinct powers of 3 else return 0.

The output for each test case is printed 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 <= 5
1 <= N <= 10^9

Time limit: 1 second

Solve now

Approaches

01 Approach

This is just the recursive implementation of the previous approach. Instead of using an iterative approach, we can use a recursive function where the base case is ‘N’ == 1.

Algorithm:

If ‘N’ == 1, return 1.
If ‘N’ %3 != 2, return validGift(‘N’ / 3).
Return 0.

Solve now

02 Approach

The idea here is that if a number’s remainder with 3 is 2 then it is impossible to write that number as a distinct power of 3 because it is not possible to make 2 with any power of 3.

So we will keep on dividing ‘N’ till we either reach ‘N’ == 0 or ‘N’ % 3 == 2.

Algorithm:

Repeat the steps until ‘N’ > 0 and ‘N’ % 3 != 2
- ‘N’ = ‘N’ / 3
If( ‘N’ % 3 == 2 )
- Return 0.
Else
- Return 1.

Solve now