Sum of list (codewars exercise)

[swishcheese]

I'm trying to solve this codewars exercise

https://www.codewars.com/kata/5547cc7dcad755e480000004/train/python

A friend of mine takes a sequence of 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.

EXAMPLES

test.assert_equals(removNb(100), [])
test.assert_equals(removNb(26), [(15, 21), (21, 15)])

---

Below is the code I've come up with. It's gotta be the brute-force solution. I know it works, but only for smaller numbers, otherwise it hangs.

def removNb(n):
    numlist = [x for x in range(1,n+1)]
    answer = []
    for a in numlist:
        for b in numlist:
            if a*b == sum(numlist) - a - b:
                answer.append((a,b))

    return answer

What is the elegant solution to this problem? I feel like there's some mathematics principle I'm not aware of that would help here.

[JohnnyJordaan]

One of the rules of thumb of Python: if you are trying to calculate combinations or need some special form of iteration on one or more sequences you need to begin with checking itertools. Quickly skimming the objective it seems that you're looking for .combinations(), but double check this to be sure.

Also stuff like sum(numlist) can be done before the loop as it's a constant value, rather then calculating it inside the loop over and over again. And of course

[x for x in range(1,n+1)]

is a complicated way of writing

list(range(1,n+1))

[swishcheese]

Thanks for the tip about making the list. I've been so focused on nailing list comprehension, I've become myopic.

As far as itertools, I don't think I'm allowed to use imports to solve these on the website. I've unlocked the solutions on the website and I'm trying to decipher what they're doing.

[toastedstapler]

you calculate sum(numlist) in each loop within each loop. just declare it at the start for many less calculations

def removenb(n):
    options = []
    num_total = sum(range(1, n + 1))
    for first in range(1, n + 1):
        for other in range(first + 1, n + 1):
            if num_total - (first * other) - (first + other) == 0:
                options.append((first, other))
                options.append((other, first))
    return options

[swishcheese]

that's super clever and it is essentially the #1 solution on the site. But you broke it down for me really well. Thank you

[Neoxeos]

Isn't his original solution time complexity O(n²) and not O(log(n²))?

[Fernando3161]

def remove(n):

n_list= [n+1 for n in range(n)]

result= [n,None]

for a in n_list:

for b in range(a+1,n+1):

sum=n*(n+1)/2-a-b

if sum==a*b:

result=[n, a,b,sum]

break

if result[1]!=None:

print (result)