Birthday Gift

Moderate

0/80

Average time to solve is 15m

1 upvote

Asked in company

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.

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 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

Sample Input 1:

Sample Output 1:

1
0
0

Explanation of Sample Output 1:

Test Case 1: We can write 28 = 3 ^ 0 + 3 ^ 3

Test Case 2: It is not possible to write 11 as the sum of distinct powers of 3.

Test Case 3: It is not possible to write 29 as the sum of distinct powers of 3.

Sample Input 2:

2
15
13

Sample Output 2:

0
1

Hint 1

Hint 2

Can you find all the valid ways of representing the given number as sum of powers of 3?

Approaches (2)

Approach 1

Approach 2

Recursive

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.

Time Complexity

O( log3(N) ), where ‘N’ is the given number.

As we are dividing ‘N’ by 3 in each operation.

Space Complexity

O( log3(N) ), where ‘N’ is the given number.

As the recursive function will store the values till it doesn't reach ‘N’ == 1.

(100% EXP penalty)

Birthday Gift

Console