Last Updated: 18 Apr, 2021
Powerful Integers
Easy
Asked in companies
Given three integers 'X', 'Y', and 'BOUND', return a list of all the powerful integers that have a value less than or equal to bound.
An integer is powerful if it can be represented as 'X'^i + 'Y'^j for some integers i >= 0 and j >= 0.
Example:
Suppose given ‘X’ is 2, ‘Y’ is 3 and ‘BOUND’ is 10 then
The list of all powerful integers is [2, 3, 4, 5, 7, 9, 10] as:
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2
Note:
1. You do not need to print anything; it has already been taken care of. Just implement the given function.
2. You may return the answer in any order. In your answer, each value should occur at most once.
Input Format
The first line of input contains a single integer ‘T’ denoting the number of test cases given. Then next ‘T’ lines follow:
The first line of each test case input contains three space-separated integers, where the first integer represents the ‘X’, the second one is ‘Y’ while the third one is ‘BOUND’.
Output Format:
For every test case, return the vector/list of all the required elements which are less than equal to the given ‘BOUND’ in any order.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraint :
1 <= T <= 1000
1 <= X, Y <= 100
0 <= BOUND <= 10^6
Time Limit: 1 sec
Approaches
We can use a simple brute force idea to calculate the bounds for the powers ‘i’ and ‘j’.
We know that at the highest bound we need to have, X^i = 10^6. Therefore, taking log to base 2 of both sides we get,
log(X^i) = log(10^6)
=> i * log X = 6 * log (10) (Since log(10) to the base 2 is approx. ~ 3.321928)
=> i * log X ~ 20
=> i = 20 / (log X)
Now, highest value of i is possible at lowest value of ‘X’, as they are inversely proportional.
=> for ‘X’ = 2
=> maximum ‘i’ = 20
So, if ‘i’ <= 20 is not applied, it will give Time Limit Exceeded.
The algorithm to calculate the required will be:-
- Initialise a set to store our results. This is because we might generate the same value multiple times. E.g. 2^1 + 3^2 = 11 and 2^3 + 3^1 = 11. But since we only need to include the value 11 once and hence, we will use a set called ‘POWERFUL_INTEGERS’ to store our answers.
- Now we iterate over the powers ‘i’ from 0 to 20 as we obtained from the above idea.
- In each iteration keep checking whether ‘X’ to power ‘i’ is less than our ‘BOUND’ and break the loop if it’s not.
- Otherwise, also iterate over the powers of ‘j’ and check if ‘X’^i + ‘Y’^j is less than ‘BOUND’.
- Add the calculated value of ‘X’^i + ‘Y’^j to our set ‘POWERFUL_INTEGERS’ if it’s smaller than ‘BOUND’ otherwise break the iteration.
- Also in every iteration, we will use the break condition to handle the scenario when ‘X’ or ‘Y’ is 1. This is because if the number ‘X’ or ‘Y’ is 1, then their power-bound will be equal to bound itself. Also, it doesn't matter what their power-bound is because 1^’N’ is always 1. Thus, when the number is 1, we don't need to loop from [0⋯’N’] and we can break early.
- Finally, return the set after converting it to a list/array.
We can use the log function to determine the bounds for the powers of ‘X’ and ‘Y’. Using this intuition, let's find out how can we calculate the bounds for the powers ‘i’ and ‘j’.
There is a way to find a much smaller bound for the powers.
- ‘M’ ^ ‘N’ <= ‘BOUND’
This formula implies that
- N <= LOGm(‘BOUND’)
The algorithm to calculate the required will be:-
- Initialise a variable ‘A’ as the power bound for the number ‘X’. Thus ‘A’ = LOGx(’BOUND’) otherwise, initialise ‘A’ to ‘BOUND’ if ‘X’ == 1.
- Similarly, initialise ‘B’ as the power bound for the number ‘Y’. Thus ‘B’ = LOGy(‘BOUND’) otherwise, initialise ‘A’ to ‘BOUND’ if ‘Y’ == 1.
- Now we will iterate on a nested for-loop structure where the outer loop will iterate from [0⋯ ‘A’] and the inner loop will iterate from [0⋯’B’].
- Initialise a set to ‘POWERFUL_INTEGERS’ to store our results as discussed in the previous approach.
- At each step, we calculate ‘X’^’A’ + ‘Y’^’B’ and check if this value is less than or equal to ‘BOUND’. If it is, then this is a powerful integer and we add it to our set of answers.
- Now in every iteration, we will use the break condition to handle the scenario when ‘X’ or ‘Y’ is 1. This is because if the number ‘X’ or ‘Y’ is 1, then their power-bound will be equal to bound itself. Also, it doesn't matter what their power-bound is because 1^’N’ is always 1. Thus, when the number is 1, we don't need to loop from [0⋯’N’] and we can break early.
- Finally, return the set after converting it to a list/array.