How to determine if x and y exist in a set of integers X that satisfies an equation

Question

I just came across an exam question whilst preparing for an exam and I'm stuck on it. The question is:

Design an algorithm which, given a set of positive integers X, determines if the equation x⁵ + xy - y² = y³ has a solution with both x and y belonging to X.

There's no programming involved, just an algorithm design. Could anyone please share their ideas?

Brute force is not acceptable

Answer 1

Pseudocode:

result = false
foreach (x in X) {
    foreach (y in X) {
        if (x^5 + x*y - y^2 == y^3) result = true
    }
}

Is something more sophisticated than this expected? If so, one can take advantage of the high-order term x^5 like this:

Sort X as a list from least to greatest.
result = false
foreach (y in X) {
    v = y*y*(y+1)
    foreach (x in X) {
        x2 = x*x
        u = x2*x2 + x*y - v
        if (u == 0) {
            result = true
            goto [DONE]
        }
        if (u > 0) goto [NEXT]
    }
    [NEXT]
}
[DONE]

Answer 2

For (really!) large input, you could:

1. Sort the list;
2. Solve the cubic equation for each number using the formula. Here assuming that each number is x, so the equation become a cubic one for y, then the formula is applicable. However this formula may take really long, and to avoid possible precision issue you could plug the answer in to check it out. Then do a binary search on the sorted list (O(logn)).

This will take asymptotically O(nlogn), but the constant factor is frightening and hidden by the big Oh nicely (well, if you are answering the question, not coding the program). Of course, if hashing is allowed (which is usually the case for interview but not necessarily for exams), this could be O(n).

Answer 3

Solve for y as a function of x: http://www.wolframalpha.com/input/?i=x%5E5%2B+xy+-+y%5E2+-+y%5E3

y(x) := INSERT_EQUATION_HERE
any((y in setX) for y in y(x) for x in setX)

This takes O(|X|), i.e. linear, time.

Alternatively, if you aren't using a language with an any function or list manipulation, then your solution has to be a bit more verbose:

for x in setX:
    possibleYs = solveForY(x)
    for y in possibleYs:
        if y in setX:
            return SOLUTION:(x,y)
return NO_SOLUTION

You don't actually have to solve the 2D polynomial like I showed above. Instead, you can consider each x in the set; this fixes x and gives you a polynomial in y. Then you solve that polynomial in a constant amount of time. For example if x=0, we'd find the 3 solutions to y^2==y^3; if x=1, we'd find the 3 solutions to 2-y^2==y^3, if x=-0.52, we'd etc. The solution is http://en.wikipedia.org/wiki/Cubic_function#General_formula_of_roots

More general version of the problem:

If you consider an arbitrary polynomial, do note that this method can only provide O(1) efficiency in the following case: min(max_x_degree, max_y_degree)<5. This is because, as proven in Galois theory, the only polynomials with certain closed-form solutions are those of degree 4 or less. And in this problem, we can just turn the variable with the highest degree into a constant.

This is not to say that O(1) efficiency could not be obtained by some other method, in cases where min(max_x_degree, max_y_degree)<5.

Things also get more interesting if you increase the number of variables.