Powerful Integers

Easy
0/40
Average time to solve is 15m
profile
Contributed by
2 upvotes
Asked in companies
MicrosoftReliance Jio Infocomm Ltd

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3 5 15
4 3 20
Sample output 1:
2 4 6 8 10 14
2 4 5 7 10 13 17 19
Explanation:
Test Case 1:


2 = 3^0 + 5^0
4 = 3^1 + 5^0
6 = 3^0 + 5^1
8 = 3^1 + 5^1
10 = 3^2 + 5^0
14 = 3^2 + 5^1    

Output [2, 4, 6, 8, 10, 14] is the required set of elements.

Test Case 2:


2 = 4^0 + 3^0
4 = 4^0 + 3^1
5 = 4^1 + 3^0
7 = 4^1 + 3^1
10 = 4^0 + 3^2
13 = 4^1 + 3^2
17 = 4^2 + 3^1
19 = 4^2 + 3^1

Output [2, 4, 5, 7, 10, 13, 17, 19] is the required set of elements.
Sample Input 2:
2
2 5 12
2 3 10
Sample output 2:
2 3 5 6 7 9
2 3 4 5 7 9 10
Hint

Try to use a simple brute force idea to solve the problem, calculating all the possible powerful integer combinations until ‘X’^i + ‘Y’^j is less than the given ‘BOUND’.

Approaches (2)
Powerful Integers

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.
Time Complexity

O(i * j), where ‘i’ and ‘j’ are the respective powers that would be used to calculate the powerful integers.

 

Since we are iterating over all the powers ‘i’ and for every ‘X’^‘i’ we are checking whether the sum of ‘Y’^’j’ and ‘X’^’i’ is less than the ‘BOUND’. Hence, the complexity here grows by O(i * j).

Space Complexity

O(i * j), where ‘i’ and ‘j’ are the respective powers that would be used to calculate the powerful integers.

 

Since, here, we require O(i * j) amount of space for storing the respective powerful integers in set, therefore, the space complexity is O(i * j).

Code Solution
(100% EXP penalty)
Powerful Integers
Full screen
Console