CODEWITHSUNDEEP
pythonoptimizationruntime
Florian
Florian

Reputation: 43

Codewars RuntimeError

I am currently trying to solve the problem "Is my friend cheating?" on Codewars. The Text are the Details to the Problem:

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).

Examples:

removNb(26) should return [(15, 21), (21, 15)]
or
removNb(26) should return { {15, 21}, {21, 15} }
or
removeNb(26) should return [[15, 21], [21, 15]]
or
removNb(26) should return [ {15, 21}, {21, 15} ]
or
removNb(26) should return "15 21, 21 15"

or

in C:
removNb(26) should return  {{15, 21}{21, 15}} tested by way of strings.
Function removNb should return a pointer to an allocated array of Pair pointers, each 
one also allocated.

My Code I tried to solve the Problem with:

def removNb(n):
    liste = [i+1 for i in range(n)]
    result = []
    for k in range(n):
        for t in range(k,n):
            m,n = liste[k], liste[t]
            if m * n == sum(liste)-(m+n):
                result.append((m, n))
                result.append((n, m)) 
    return result

This solution is working, but appently not enough optimised.

Does anyone have an idea how to optimize the Code further.

Upvotes: 0

Views: 374

Answers (2)

Samwise
Samwise

Reputation: 71522

Since you never mutate this list:

liste = [i+1 for i in range(n)]

it's always just [1, ..., n], so you can replace any expression of the form liste[x] with just x + 1. And instead of computing sum(liste) repeatedly, you can just do it once. Applying those changes leaves you with:

def removNb(n):
    total = sum(range(n + 1))
    result = []
    for k in range(n):
        for t in range(k, n):
            m, n = k + 1, t + 1
            if m * n == total - (m + n):
                result.append((m, n))
                result.append((n, m))
    return result

We can further eliminate the + 1s by modifying our ranges:

def removNb(n):
    total = sum(range(n + 1))
    result = []
    for k in range(1, n + 1):
        for t in range(k, n + 1):
            m, n = k, t
            if m * n == total - (m + n):
                result.append((m, n))
                result.append((n, m))
    return result

which also makes the m, n assignment superfluous (also shadowing n inside the loop was confusing):

def removNb(n):
    total = sum(range(n + 1))
    result = []
    for k in range(1, n + 1):
        for t in range(k, n + 1):
            if k * t == total - (k + t):
                result.append((k, t))
                result.append((t, k))
    return result

Upvotes: 2

BrokenBenchmark
BrokenBenchmark

Reputation: 19253

You're recomputing sum(liste) for every iteration of the inner loop. This takes your runtime from O(n^2) to O(n^3).

Here's a quick fix:

def removNb(n):
    nums = list(range(1, n + 1))
    result = []
    total = sum(nums)
    for k in range(n):
        for t in range(k,n):
            m, n = nums[k], nums[t]
            if m * n == total - (m + n):
                result.append((m, n))
                result.append((n, m)) 
    return result

print(removNb(26))

If that still isn't fast enough, you can also cut down the runtime from O(n^2) to O(n log n) by using a binary rather than linear search in the inner loop.

Upvotes: 1

Related Questions