Solution: Powerful Integers

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #970 (Medium): Powerful Integers

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

Examples:

Example 1:
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

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

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

This problem is a pretty straightforward one. Since we need to return all powerful integers and not just a count of them, there aren't many shortcuts we can take; we'll have to actually come up with the solution iteratively with nested loops.

First, we can use a set structure (ans) 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.

One somewhat tricky situation occurs when one or more of the values is a 1, as that power will continue to be 1 forever, regardless of the exponent. To deal with that, we can force each nested loop to break after the first iteration if its original value was a 1.

Once we've iterated over all possible combinations, we can convert ans to an array and return it.

Implementation:

There are only minor differences in the code of each language.

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var powerfulIntegers = function(x, y, bound) {    let ans = new Set()    for (let xi = 1; xi < bound; xi *= x) {        for (let yj = 1; xi + yj <= bound; yj *= y) {            ans.add(xi + yj)            if (y === 1) break        }        if (x === 1) break    }    return Array.from(ans)}

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:    def powerfulIntegers(self, x: int, y: int, bound: int) -> List[int]:        ans, xi = set(), 1        while xi < bound:            yj = 1            while xi + yj <= bound:                ans.add(xi + yj)                if y == 1: break                yj *= y            if x == 1: break            xi *= x        return list(ans)

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {    public List<Integer> powerfulIntegers(int x, int y, int bound) {        Set<Integer> ans = new HashSet<>();        for (int xi = 1; xi < bound; xi *= x) {            for (int yj = 1; xi + yj <= bound; yj *= y) {                ans.add(xi + yj);                if (y == 1) break;            }            if (x == 1) break;        }        return new ArrayList<Integer>(ans);    }}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {public:    vector<int> powerfulIntegers(int x, int y, int bound) {        unordered_set<int> ans;        for (int xi = 1; xi < bound; xi *= x) {            for (int yj = 1; xi + yj <= bound; yj *= y) {                ans.insert(xi + yj);                if (y == 1) break;            }            if (x == 1) break;        }        return vector<int>(ans.begin(), ans.end());    }};