Powerful Integers by Bruteforce Algorithm using C++


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

C++ Bruteforce Algorithm to Compute the Powerful Integers

The edge cases are when x and y are equal to 1. We can use a set to store the unique powerful integers within the bound. If X = 1 or Y = 1, the time complexity is tex_ae24efb64b3ed0d3dfe2371042f7e026 Powerful Integers by Bruteforce Algorithm using C++ algorithms brute force c / c++ math . If both are 1, then the complexity is O(1) – as there is only 1 powerful integer, which is 1+1=2.

If neither X or Y is 1, the time complexity is tex_b4b78692493ec8febd08e69d8fe3efe6 Powerful Integers by Bruteforce Algorithm using C++ algorithms brute force c / c++ math . The space complexity is the same the time complexity as each number to test may be a potential powerful integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> data;
        int a, b;
        for (int i = 0; (a = pow(x, i)) <= bound; ++ i) {
            for (int j = 0; (b = a + pow(y, j)) <= bound; ++ j) {
                if (b <= bound) {
                    data.insert(b);
                } else break;
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        vector<int> res;
        std::copy(data.begin(), data.end(), std::back_inserter(res));
        return res;
    }
};
class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> data;
        int a, b;
        for (int i = 0; (a = pow(x, i)) <= bound; ++ i) {
            for (int j = 0; (b = a + pow(y, j)) <= bound; ++ j) {
                if (b <= bound) {
                    data.insert(b);
                } else break;
                if (y == 1) break;
            }
            if (x == 1) break;
        }
        vector<int> res;
        std::copy(data.begin(), data.end(), std::back_inserter(res));
        return res;
    }
};

And, if either X or Y is 1, we can break the loop – as 1 to the power of any will be still one, otherwise, it will be an endless loop. At last, we need to convert the set to std::vector in C++ and in this post, there are quite a few methods to do that.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
463 words
Last Post: How to Check if Any Three Points can Make a Triangle?
Next Post: CloudFlare Enterprise Plan Overview

The Permanent URL is: Powerful Integers by Bruteforce Algorithm using C++

Leave a Reply