Interview Question
Country: India
I solved it by storing all numbers from 1 to x, which could be obtained by raising numbers to the different powers greater than 1. Then just loop through all numbers between 1 and x and check if k and (x - k) are stored as powers of some other numbers.
time complexity: O(x * log x)
memory complexity: O(x)
void solve_equation(int x, int &a, int &b, int &n, int &m)
{
a = b = n = m = 0;
// powers[i] == (d, p) iff d^p == i
vector < pair < int, int > > powers(x + 1, make_pair(0, 0));
powers[1] = make_pair(1, 2);
for (int i = 2; i * i <= x; ++i)
{
int d = i;
int p = 1;
while (d * i <= x)
{
d = d * i;
p++;
powers[d] = make_pair(i, p);
}
}
for (int i = 1; i <= x; ++i)
if (powers[i].first != 0 && powers[x - i].first != 0)
{
a = powers[i].first;
n = powers[i].second;
b = powers[x - i].first;
m = powers[x - i].second;
}
}
I would first do some preprocessing in order to get a set of numbers that are perfect powers less than 1000000. Start from i=2. For each i, keep raising its power till we exceed 1000000, while adding the number to the set. Note that we can stop at 1000 because 1000^2 = 1000000 already. Also note that 2^20 > 1000000, which means this preprocessing will take at most 20*1000 = 20000 operations.
After the preprocessing, we have a set that's <20000 elements. To check whether N can be expressed as the sum of 2 perfect powers, we can simply iterate through the set and check whether N - "current element" is also in the set.
The answer depends on how frequently would you query for x being a sum of powers.
- Subbu. December 02, 2013