Powerful Integers: A Brute Force Optimization Lesson

Given two non-negative integers x and y, an integer is powerful if it equals x^i + y^j for some integers i ≥ 0 and j ≥ 0.

The task: return all powerful integers with values ≤ bound. Each value appears once.

First Approach

I computed all powers of x and y under bound ahead of time. Then I iterated through sums, checking if (sum - x_power) existed in the y_powers table.

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        vector<int> res;
        if (bound < 2) {
            return res;
        }
        res.push_back(2);
        
        if (bound < x || bound <y) {
            return res;
        }
        
        vector<int> xs;
        xs.push_back(1);
        if (x > 1) {
          int p = x;
          while(p<bound) {
            xs.push_back(p);
            p*=x;
          }
        }

        
        set<int> ys;
        ys.insert(1);
        if (y > 1) {
            int p = y;
            while(p<bound) {
                ys.insert(p);
                p*=y;
            }
        }

        
        for(int b=3;b<=bound;b++) {
            for(int j=0;j<xs.size();j++) {
                if (xs[j] >= b) {
                    break;
                }
                
                if (ys.find(b-xs[j]) != ys.end()) {
                    res.push_back(b);
                    break;
                }
            }
        }
        return res;
    }
};

This worked but did too much work upfront.

Better Approach: Direct Enumeration

Instead of computing sums, I enumerated powers directly. This cut computation dramatically.

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        unordered_set<int> s;
        for (int i = 1; i < bound; i *= x) {
            for (int j = 1; i + j <= bound; j *= y) {
                s.insert(i + j);
		// if y is 1, we only need one iteration before moving to next x
                if (y == 1) break;
            }
	    // if x is 1, we only need one full y iteration then exit
            if (x == 1) break;
        }
        return vector<int>(s.begin(), s.end());
    }
};

Key Insight

When enumerating, choose smaller search spaces. The unordered_set gave me O(1) insertions, avoiding vector resizing costs.

#bruteforce #hashset

Path Sum in Binary Trees Powers of N: Two Ways to Check