Question

Formatted question description: https://leetcode.ca/all/970.html

Given two positive integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

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

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]
Note:

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

Algorithm

This question defines a powerful integer, which is the sum of the i power and j power of a given integer x and y respectively. Now an integer bound is given, so that all powerful integers that do not exceed this range are returned.

Since it’s an Easy topic, don’t think about too many techniques, just crack it without thinking. The initial solution of the blogger is to generate x and y exponent arrays in the bound range, namely x^0, x^1, x^2… and y^0, y^1, y^2. …, and then take any number from each of the two arrays and add them together. As long as it does not exceed bound, it can be put into the result res. It should be noted that if x and y are equal to 1, then you will fall into death Loop, because multiplying by 1 is always equal to itself, so additional judgments must be added.

The method can actually be optimized, there is no need to use an additional array to save, but can be processed directly in the for loop. Also, in order to prevent duplicate numbers, first store the results in a TreeSet, take advantage of the feature that can remove duplicates, and finally turn back to the array. See the code as follows:

Code

C++

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        set<int> res;
        for (int a = 1; a < bound; a *= x) {
            for (int b = 1; a + b <= bound; b *= y) {
                res.insert(a + b);
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        return vector<int>(res.begin(), res.end());
    }
};

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        List<Integer> xList = new ArrayList<Integer>();
        List<Integer> yList = new ArrayList<Integer>();
        int xNum = 1, yNum = 1;
        if (x == 1)
            xList.add(1);
        else {
            while (xNum <= bound) {
                xList.add(xNum);
                xNum *= x;
            }
        }
        if (y == 1)
            yList.add(1);
        else {
            while (yNum <= bound) {
                yList.add(yNum);
                yNum *= y;
            }
        }
        List<Integer> powerfulIntegers = new ArrayList<Integer>();
        int xSize = xList.size(), ySize = yList.size();
        for (int i = 0; i < xSize; i++) {
            int numX = xList.get(i);
            for (int j = 0; j < ySize; j++) {
                int numY = yList.get(j);
                int sum = numX + numY;
                if (sum > bound)
                    break;
                if (!powerfulIntegers.contains(sum))
                    powerfulIntegers.add(sum);
            }
        }
        Collections.sort(powerfulIntegers);
        return powerfulIntegers;
    }
}

############

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

// OJ: https://leetcode.com/problems/powerful-integers/
// Time: O(log_x^bound * log_y^bound)
// Space: O(log_x^bound * log_y^bound)
class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> s;
        for (int a = 1; a + 1 <= bound; a = x == 1 ? bound : a * x) 
            for (int b = 1; a + b <= bound; b = y == 1 ? bound : b * y) 
                s.insert(a + b);
        return vector<int>(s.begin(), s.end());
    }
};

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

############

class Solution(object):
    def powerfulIntegers(self, x, y, bound):
        """
        :type x: int
        :type y: int
        :type bound: int
        :rtype: List[int]
        """
        res = set()
        i = 0
        while x ** i <= bound and i <= bound:
            j = 0
            while j <= bound:
                target = x ** i + y ** j
                if target > bound:
                    break
                res.add(target)
                j += 1
            i += 1
        return list(res)

/**
 * @param {number} x
 * @param {number} y
 * @param {number} bound
 * @return {number[]}
 */
var powerfulIntegers = function (x, y, bound) {
    let res = new Set();
    for (let i = 1; i < bound; i *= x) {
        for (let j = 1; j < bound; j *= y) {
            if (i + j <= bound) {
                res.add(i + j);
            }
            if (y == 1) break;
        }
        if (x == 1) break;
    }
    return [...res];
};

func powerfulIntegers(x int, y int, bound int) (ans []int) {
	s := map[int]struct{}{}
	for a := 1; a <= bound; a *= x {
		for b := 1; a+b <= bound; b *= y {
			s[a+b] = struct{}{}
			if y == 1 {
				break
			}
		}
		if x == 1 {
			break
		}
	}
	for x := range s {
		ans = append(ans, x)
	}
	return ans
}

function powerfulIntegers(x: number, y: number, bound: number): number[] {
    const ans = new Set<number>();
    for (let a = 1; a <= bound; a *= x) {
        for (let b = 1; a + b <= bound; b *= y) {
            ans.add(a + b);
            if (y === 1) {
                break;
            }
        }
        if (x === 1) {
            break;
        }
    }
    return Array.from(ans);
}

970 - Powerful Integers

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions