Skip to main content

Powerful Integers

Problem Description​

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.

You may return the answer in any order. In your answer, each value should occur at most once.

Examples​

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
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

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Constraints​

  • 1 <= x, y <= 100
  • 0 <= bound <= 10^6

Solution for Powerful Integers Problem​

To solve this problem, we need to find all unique integers that can be represented as x^i + y^j and are less than or equal to bound. We iterate over possible values of i and j while ensuring the results stay within the bounds.

Approach​

  1. Iterate Over Powers:

    • For x, calculate powers x^i starting from i = 0 and stopping when x^i > bound.
    • For each x^i, calculate powers y^j starting from j = 0 and stopping when y^j > bound.
    • If x^i + y^j <= bound, add it to the result set to ensure uniqueness.
  2. Handling Edge Cases:

    • If x == 1, then x^i will always be 1 for all i, so the loop should run only once for i = 0.
    • Similarly, if y == 1, then y^j will always be 1.

Code in Different Languages​

Written by @ImmidiSivani
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
set<int> resultSet;
for (int i = 1; i < bound; i = (x == 1) ? bound : i * x) {
for (int j = 1; i + j <= bound; j = (y == 1) ? bound : j * y) {
resultSet.insert(i + j);
}
}
return vector<int>(resultSet.begin(), resultSet.end());
}
};

Complexity Analysis​

  • Time Complexity: O(logx(textbound)∗logy(textbound))O(log_x(text{bound})*log_y(text{bound})), since we iterate logarithmically based on the bound.
  • Space Complexity: O(k)O(k), where k is the number of unique powerful integers found.

Authors:

Loading...