4
\$\begingroup\$

This is my first working 2sum solver. It works by finding the difference for our target in s to determine if that 2sum exists.

Suppose our target is -5. I start with the first index in s and use subtraction, (-5-(-8) = 3), and the result is 3. The code will check the difference in s. If the difference exists in the list s then the output is yes.

s = [-8,3,5,1,3]
target = -5

for j in range(0, len(s)):
  if target-int(s[j]) in s[j+1:len(s)]:
   print('yes')
   quit()

print('no')

I fixed a bug where a false yes was returned when int(s[j]) was equal to target-int(s[j]). I did this by s[j+1:len(s)] An example would be our target would be 4, but our input for s was [2]. It would say yes because int(s[j]) was equal to target-int(s[j]).

Is it possible to write this code all in one or two lines of code?

\$\endgroup\$
  • \$\begingroup\$ When mentioning about target = 4 for s = [2] which gives you yes, did you describe the wrong case? Because your current approach will output no for that input case. \$\endgroup\$ – RomanPerekhrest Jan 25 at 19:08
  • \$\begingroup\$ @RomanPerekhrest I'm stumped on it. I got writer's block. I'll figure out how I should best explain it. \$\endgroup\$ – Travis Wells Jan 25 at 19:57
  • \$\begingroup\$ Why the int(...) conversions if the inputs are already integers? Is the function meant to also work with non-integer inputs? If so, is the rounding behaviour of int really what you want? \$\endgroup\$ – kaya3 Jan 26 at 2:14
  • 2
    \$\begingroup\$ What is the reason you want to write it in one or two lines? I often see code that's really hard to understand just because the developer have prioritized few lines over readability. This causes bugs and maintenance problems. There are of course many good reasons to change the code to few lines, just make sure to not use few lines as a goal. \$\endgroup\$ – Polygorial Jan 26 at 19:27
5
\$\begingroup\$

Translating your code directly into a one-liner:

s = [-8,3,5,1,3]
target = -5

is_2sum = any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))
print(is_2sum)

A few notes:

  • The loop is now translated into a generator expression: we record whether every difference is present in the remainder of the list and combine this with any, which will check if the resulting list contains a True.

  • In particular, note that we do not construct a list by list comprehension inside the call to any. Indeed, by using a generator expression we allow for an early exit as soon as a True value is found, potentially speeding up quite a bit the execution on positive instances.

  • Your approach runs in quadratic time. However, this algorithm can be further optimized to run in linear time (see e.g., a similar question on CS.SE).

If you are fine with a quadratic time algorithm, another alternative is to brute-force every pair. It is straightforward to generalize such an algorithm to k-sum as well. So just for fun, we might also do:

from itertools import combinations 

s = [-8,3,5,1,3]
target = -5

is_2sum = any(sum(p) == target for p in combinations(s, 2))
print(is_2sum)

As stated, this is not highly scalable, but it should very easy for a beginner to read and to understand (if that matters).

\$\endgroup\$
  • \$\begingroup\$ I was trying to make it a little faster than O(n^2) time by stopping one element short because of s[j+1:len(s)]. \$\endgroup\$ – Travis Wells Jan 30 at 2:54
  • \$\begingroup\$ @TravisWells Such an approach runs in big Omega of n squared, so that won't help. \$\endgroup\$ – Juho Jan 30 at 5:49
4
\$\begingroup\$
  • You should make this a function.
  • You should use 4 spaces for indentation.
  • If s becomes a count of numbers in a dictionary, then in becomes performs in \$O(1)\$ time, where lists perform in \$O(n)\$ time.
  • Using quit isn't really idiomatic, and was added to make exiting the REPL easier.
  • Rather than for j in range(0, len(s)) you can use for item in s.
  • Use better variable names, s and j are just meh.
  • You can use a comprehension, with any to reduce noise.
import collections


def has_two_sum(items, target):
    items = collections.Counter(map(int, items))
    for item in map(int, items):
        remainder = target - item
        if items.get(remainder, 0) >= (2 if item == remainder else 1):
            return True
    return False


if has_two_sum(s, target):
    print('yes')
else:
    print('no')

Or you can write it in on of these one liners, which look like garbage:

s=collections.Counter(map(int,s));print(['no','yes'][any(map(lambda i:s.get(t-i,0)>=1+(i==t-i),s))])
f=set();print(['no','yes'][any(map(lambda i:(t-i in f,f.add(i))[0],s))])
\$\endgroup\$
  • \$\begingroup\$ This will have the same bug that the OP described where a number plus itself can equal the target, giving a "false yes". You can fix it by putting each number into the set after testing it, instead of putting them all in at the start. \$\endgroup\$ – kaya3 Jan 26 at 2:16
  • \$\begingroup\$ Yes @kaya3, there is that bug indicating insufficient testing. On the other hand I like presenting code that is well formatted rather than golfed into a minimum number of lines. I do have one formatting quibble, I don't like simplistic if/else blocks. print(f'{"yes" if has_two_sums(s,target) else "no"}') \$\endgroup\$ – verisimilidude Jan 26 at 5:15
  • 1
    \$\begingroup\$ No need for a format string there - print("yes" if has_two_sums(s, target) else "no") is equivalent. \$\endgroup\$ – kaya3 Jan 26 at 5:49
  • \$\begingroup\$ @kaya3 Ah yes, my last 2 sum didn't have that characteristic. Simple fix. \$\endgroup\$ – Peilonrayz Jan 26 at 12:13
1
\$\begingroup\$

I believe this will solve your problem:

# Using ternary operator to condense the print's
two_sum = lambda s, target: print('yes') if any(map(lambda x: target-x in s and s.count(x)>1, s)) else print('no')

# If s.count(x) is 1, it means the subtraction resulted in the same element took that time for the operation, which we don't want to happen. So the count must be greater then 1

two_sum([-8, 3, 5, 1, 3], -5)
# Output is "yes"

two_sum([2], 4)
# Output is "no"

So, we wrapped the function in a lambda, used another lambda in the map call and preserved all items in the list, checking if the output matches another element besides the one took in for the calculation.

Benchmark

I was wondering if @Juho's answer provided a faster function, so I benchmarked both.

So:

two_sum = lambda s, target: any(map(lambda x: target-x in s and s.count(x)>1, s))

is_2sum = lambda s, target: any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))

# The print's aren't necessary for the benchmark.

Then, I ran both at Google Colab with the following code:

two_sum = lambda s, target: any(map(lambda x: target-x in s and s.count(x)>1, s))

is_2sum = lambda s, target: any(target - s[j] in s[j+1:len(s)] for j in range(len(s)))

test_function = two_sum
# test_function = is_2sum

if __name__ == "__main__":
    import timeit
    setup = "from __main__ import test_function"
    average=0
    for i in range(0,100):
      average=average+timeit.timeit("test_function([-8, 3, 1, 5, 1, 3], -5)", setup=setup, number=1000000)
    print(average/100)

The method timeit.timeit() will run each function 1.000.000 times, then I record the outputs of 100 iterations (so, we actually ran the function 100.000.000 times) and take the average.

Results:

For the function two_sum:
First run: 0.9409843384699957
Second run: 0.948360692339993

For the function is_2sum:
First run: 0.9963176720300112
Second run: 0.998327726480004

As you can see, there is an increase in performance for two_sum function, whether this comes from the use of map() and avoiding lists operations, I don't know, but it's a bit faster.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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