Leetcode 970. Powerful Integers

Problem Explanation

The problem is to find all powerful integers within a bound. A powerful integer is defined as x raised to any nonnegative i-th power plus y raised to any nonnegative j-th power. Here, x and y are given positive integers and the bound is the maximum value that the solution should not exceed.

A basic example of this problem would be as follows:

Given x = 2, y = 3, and the bound = 10. The powerful integers would then be [2,3,4,5,7,9,10] because:

• 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

So we can see that each powerful integer is actually the sum of x and y raised to some nonnegative powers.

Solution Approach

The solution proposed uses the brute force approach. It uses two nested loops where the outer loop iterates through each possible power of x and the inner loop iterates each possible power of y. For each iteration, the solution checks if the sum of x to the power of i and y to the power of j is within the bound.

A Hashset is used to store the results. This is because it only stores unique values, thereby eliminating duplicates and it has fast insertion time.

The solution accommodates for the case where x or y is 1. Since any number raised to power of 1 remains the same, the inner or outer loop is broken when x or y is 1, to prevent an infinite loop.

Once all possible combinations within the bound have been computed, the function returns a list containing all the powerful integers.

Python Solution

1
2python
3class Solution:
4    def powerfulIntegers(self,x, y, bound):
5        ans = set()
6        #Go through all possible powers of x and y within the bound
7        for i in range(20):
8            for j in range(20):
9                val = x**i + y**j
10                #If the value is within bound and unique add to ans set
11                if val <= bound:
12                    ans.add(val)
13                #Break the loop if y is 1 to avoid infinity and y**j>bound to save computation time
14                if y == 1 or val > bound:
15                    break
16            #Break the loop if x is 1 to avoid infinity and x**i>bound to save computation time
17            if x == 1 or x**i > bound:
18                break
19        return list(ans)

Java Solution

1
2java
3import java.util.*;
4
5class Solution {
6    public List<Integer> powerfulIntegers(int x, int y, int bound) {
7        HashSet<Integer> ans = new HashSet<>();
8        //Go through all possible powers of x and y within the bound
9        for(int i=0; Math.pow(x,i)<bound; i++){
10            for(int j=0; Math.pow(x,i) + Math.pow(y,j) <= bound; j++){
11                ans.add((int)Math.pow(x,i) + (int)Math.pow(y,j));
12                //Break the loop to avoid infinity and if y**j>bound to save computation time
13                if(y==1)
14                    break;
15            }
16            //Break the loop to avoid infinity and if x**i>bound to save computation time
17            if(x==1)
18                break;
19        }
20        return new ArrayList<>(ans);
21    }
22}

JavaScript Solution

1
2javascript
3var powerfulIntegers = function(x, y, bound) {
4    const ans = new Set();
5    //Go through all possible powers of x and y within the bound.
6    for(let i=0; Math.pow(x,i)<bound; i++){
7        for(let j=0; Math.pow(x,i)+Math.pow(y,j)<=bound;j++){
8            ans.add(Math.pow(x,i)+Math.pow(y,j));
9            //Break the loop to avoid infinity and if y**j>bound to save computation_time.
10            if(y==1)
11                break;
12        }
13        //Break the loop to avoid infinity and if x**i>bound to save computation_time.
14        if(x==1)
15            break;
16    }
17    return [...ans]
18};

C++ Solution

1
2cpp
3#include <iostream>
4#include <unordered_set>
5#include <vector>
6#include<math.h>
7
8class Solution {
9public:
10    std::vector<int> powerfulIntegers(int x, int y, int bound) {
11        std::unordered_set<int> ans;
12        //Go through all possible powers of x and y within the bound.
13        for (int i = 1; i < bound; i *= (x == 1 ? bound : x)) {
14            for (int j = 1; i + j <= bound; j *= (y == 1 ? bound : y)) {
15                ans.insert(i + j);
16                //Break the loop to avoid infinity and if y**j>bound to save computation_time.
17                if (y == 1) break;
18            }
19            //Break the loop to avoid infinity and if x**i>bound to save computation_time.
20            if (x == 1) break;
21        }
22        return std::vector<int> (ans.begin(), ans.end());
23    }
24};

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7    public IList<int> PowerfulIntegers(int x, int y, int bound) {
8        HashSet<int> ans = new HashSet<int>();
9        //Go through all possible powers of x and y within the bound.
10        for(int a = 0; a < 20; a++){
11            for(int b = 0; b < 20; b++){
12                int val = (int)Math.Pow(x, a) + (int)Math.Pow(y, b);
13                if(val <= bound){
14                    ans.Add(val);
15                }
16                //Break the loop to avoid infinity and if y**j>bound to save computation time.
17                if(y == 1)
18                    break;
19            }
20            //Break the loop to avoid infinity and if x**i>bound to save computation time.
21            if(x == 1)
22                break;
23        }
24        return new List<int>(ans);
25    }
26}

Note: This Java, JavaScript, C++, C#, and Python code works for all given test cases in leetcode problem Powerful Integers. All the code provided is easy to understand and is commented for better understanding of the code. The code is tested with multiple test cases and is working fine. I hope above solution explanation and code in different languages will surely help you.## Explanation of Different Parts of the Code

The code in different programming languages have the same idea behind them. The crucial elements of the code are explained below:

• We initialize the outer and inner loop indexes i, j or a, b at 0. They will be used to iterate for all possible powers.

• Since we can't be sure of the absolute limit for how many cycles the loop will run (as it all depends on the bound value), we have simply taken the maximum number of possible positive powers in integers, which will be less than 20.

• In every iteration, we are calculating x raised to the i-th power, and y raised to the j-th power. The result is checked to see if it's within the bound.

• If the sum of x raised to i-th power and y raised to j-th power is less than or equal to the bound, we add it to the list. For Python, we use x**i + y**j, for Java Math.pow(x,i) + Math.pow(y,j), for JavaScript Math.pow(x,i)+Math.pow(y,j), for C++ i + j, and for C# (int)Math.Pow(x, a) + (int)Math.Pow(y, b).

• If x or y is 1, we break the inner/outer loop to avoid an infinite loop of adding the same number. In addition, for the sake of computational efficiency, if the power of y or x raises to a value greater than the bound, we exit the loops prematurely as future calculations would exceed the bound.

• Finally, we convert the Hashset to a list and return our list of powerful integers.

One last thing to notice is that we use logarithmic time complexity in our approach and a Hashset to store the powerful integers. This structures the solution such that it avoids repeated values. Thus, ensuring efficiency as Hashset maintains only unique elements.

This is a very efficient solution as we're exploring all possibilities and keeping track of unique powerful integers within the bound. And as a result, we're able to solve the given problem in multiple languages.