Difficulty: Medium Link: Day 30: April Leetcoding Challenge
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 xi + yj for some integers i >= 0 and j >= 0. You may return the answer in any order. In your answer, each value should occur at most once.
Input: x = 2, y = 3, bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 20 + 30 3 = 21 + 30 4 = 20 + 31 5 = 21 + 31 7 = 22 + 31 9 = 23 + 30 10 = 20 + 32
Input: x = 3, y = 5, bound = 15 Output: [2,4,6,8,10,14]
1 <= x, y <= 100
0 <= bound <= 106
The problem is simply find out the integers (i , j) which satisfy the condition xi + yj <= bound. We can use brute force to iterate with two nested loops and check if sum of both terms is less than bounds. We can use a set structure to prevent duplicate answers. Then we can have our nested loops increment the power of the x and y values while adding the appropriate results to our set. The maximum value of any terms compounded with x or y is bound – 1 (Why because x, y >= 1, so if any of them becomes 1 then the maximum value of other term = bound – 1).
We need to take care of the case when x or y = 1. Let us say y = 1, then for every power i, yi = 1 and it will become an infinite loop. So in the end of the consecutive loops , we can check for x = 1 and y = 1 and break out because all the possible values of other terms would have been achieved in the current iteration.
The operations it takes x to reach bounds is LogX(Bound). Similarly the max operations for y to reach bounds is LogY(Bound). Therefore total operations would be in order of O(LogX(Bound) * LogY(Bound)) which is huge because with increasing powers, there would be limited integers satisfying the conditions. Same would be for space.
Time = O(LogX(Bound) * LogY(Bound))
Space = O(LogX(Bound) * LogY(Bound))