Find numbers whose product equals the sum of the rest of the range

Question

Instructions for the 'is my friend cheating' kata in codewars are:

A friend of mine takes the sequence of all numbers from 1 to n (where n > 0).

Within that sequence, he chooses two numbers, a and b.

He says that the product of a and b should be equal to the sum of all numbers in the sequence, excluding a and b.

Given a number n, could you tell me the numbers he excluded from the sequence?

The function takes the parameter: n (n is always strictly greater than 0) and returns an array or a string (depending on the language) of the form:

[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or or [{a, b}, ...] with all (a, b) which are the possible removed numbers in the sequence 1 to n.

[(a, b), ...] or [[a, b], ...] or {{a, b}, ...} or ... will be sorted in increasing order of the "a".

It happens that there are several possible (a, b). The function returns an empty array (or an empty string) if no possible numbers are found which will prove that my friend has not told the truth! (Go: in this case return nil).

def remov_nb(n):
    lst=[]

    
    for x in range(1,n+1):
        for y in range(1,n+1):
            if (n*(n+1))/2-x-y==x*y:
                lst.append((x,y))
    return lst

My code passes the simple tests but times out on the challenge inputs.

Answer 1

If (a, b) is a solution, then we know that (b, a) is a solution, so we only need to search half the problem space.

The sum of range 1..n (n*(n+1)/2) never changes within the function, so we could pre-calculate that.

To get away from the quadratic scaling, we're going to have to do something cleverer than brute-force search. Consider starting with the sum of the range (call that s), and see where dividing s-a by a gets you. There will only be one or two b values worth considering, which gets closer to linear scaling.

Style: remove the blank lines, and add space around operators.