2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I'm curious why everywhere you write about a and b, then in the code you use x and y? \$\endgroup\$
    – slepic
    Dec 7, 2022 at 19:55
  • \$\begingroup\$ Are you allowed to use numba(python code speeding module) \$\endgroup\$
    – Kimi M
    Aug 15, 2023 at 19:41

1 Answer 1

6
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Excellent answer. To build on the comment about "(s-a)/a", one can actually go further.By looking for solutions (a, a+b), once you have a candidate for a, there is a single candidate solution for b which can be determined formally (s - a(a+2))/(a+1) \$\endgroup\$
    – SylvainD
    Dec 7, 2022 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.