DEV Community

Cover image for Solution: Powerful Integers
seanpgallivan
seanpgallivan

Posted on

4 2

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)
}
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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());
    }
};
Enter fullscreen mode Exit fullscreen mode

SurveyJS custom survey software

JavaScript UI Libraries for Surveys and Forms

SurveyJS lets you build a JSON-based form management system that integrates with any backend, giving you full control over your data and no user limits. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay