Given is an integer N. Determine whether there is a pair of positive integers (A,B) such that
3^A+5^B=N, and find one such pair if it exists.If no such pair exist then return -1.
N=106
Ans: A=4 ,B=2
N=1024
Ans:-1
I think you can do it using brute force. Look for all values of B for which 5^B < n. And then loop over i to check if (n-5^i) is a perfect power of 3 , which can be easily checked in log n time per loop turn.
So overall complexity O(log^2n)
1 Like
This post was flagged by the community and is temporarily hidden.
got the wrong answer from 7th case
N can be as large as 10^18, so the largest power of 3 that is less than 10^18 is roughly log base 3 of 10^18, which is around 40. So brute force over all the powers of 3 from 1 to 40, and check if (N- 3^i) is a power of 5. Also notice that ‘a’ and ‘b’ have to be positive integers, so they cannot be 0. So basically if you split 10 as 3^2 + 5^0, then it is invalid in this case.
1 Like