Sponsored
Sponsored
This approach involves iterating over possible powers of x and y, and calculating their sums while keeping the sum within the bound. We use two nested loops: one to iterate over powers of x and the other to iterate over powers of y. The results are stored in a set to ensure uniqueness.
Time Complexity: O(log(bound)^2) since the loops iterate logarithmically with respect to the bound.
Space Complexity: O(n) where n is the number of unique powerful integers within the bound.
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <cmath>
5
6std::vector<int> powerfulIntegers(int x, int y, int bound) {
7 std::unordered_set<int> powerful;
8 for (int i = 0; pow(x, i) <= bound && i < 20; ++i) {
9 for (int j = 0; pow(y, j) <= bound; ++j) {
10 int sum = pow(x, i) + pow(y, j);
11 if (sum <= bound) {
12 powerful.insert(sum);
13 }
14 if (y == 1) break;
15 }
16 if (x == 1) break;
17 }
18 return std::vector<int>(powerful.begin(), powerful.end());
19}This function in C++ also iterates over possible powers of x and y and inserts valid sums into a std::unordered_set to avoid duplicates. It takes advantage of the pow function to compute powers and uses nested loops to generate combinations of i and j. The function returns the set contents as a vector.
In this approach, we optimize the early termination condition by ensuring that we stop iterating as soon as additional powers do not contribute to any new sums within the bound. This prevents unnecessary iterations and computations.
Time Complexity: O(log(bound)^2) as it bounds progression over the log of the bound value.
Space Complexity: O(n) where n is the number of unique powerful integers.
1function powerfulIntegers(x, y, bound) {
This JavaScript function employs a similar logic to previous approaches but uses multiplicative updates instead of powers for progression through x^i and y^j. It utilizes Set for uniqueness and converts the result to an array for the final output.