Two number Sum program in python O(N^2)

Question

I am used to write code in c++ but now I am trying to learn python. I came to know about the Python language and it is very popular among everyone. So I thought, let's give it a shot.

Currently I am preparing for companies interview questions and able to solve most of them in c++. Alongside which, I am trying to write the code for the same in Python. For the things which I am not familiar with, I do a google search or watch tutorials etc.

While I was writing code for my previously solved easy interview questions in python, I encountered a problem.

Code : Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Given an array of integers, print the indices of the two numbers such that they add up to a specific target.

def twoNum(*arr, t):
  cur = 0
  x = 0
  y = 0

  for i in range (len(arr) - 1):

      for j in range (len(arr) - 1):
          if(i == j):
              break
          cur = arr[i] + arr[j]
          if(t == cur):
              x = arr[i]
              y = arr[j]
              break

      if(t == cur):
          break

  print(f"{x} + {y} = {x+y} ")

arr = [3, 5, -4, 8, 11, 1, -1, 6]

target = 10

twoNum(arr, t=target)

So here is the problem: I have defined x, y in function and then used x = arr[i] and y = arr[j] and I m printing those values.

output coming is : is 0 + 0 = 10 (where target is 10)

This is I guess probably because I am using x = 0 and y = 0 initially in the function and it seems x and y values are not updating then I saw outline section in VSCode there I saw x and y are declared twice, once at the starting of the function and second in for loop.

Can anyone explain to me what is going on here?

For reference, here is an image of the code I wrote in C++

This image is my code written in cpp,

Why did you add an asterisk on the first parameter? Even in your C++, the parameter's name is just "arr" – the * is part of its type. (Read the documentation for details.) — molbdnilo
– molbdnilo, Commented Apr 2, 2020 at 10:53
Change def twoNum(*arr,t): to def twoNum(arr,t): and your program should work. — DarrylG
– DarrylG, Commented Apr 2, 2020 at 10:53
This is a well known problem which can be solved in O(n) rather than O(n^2) as described here using hashing. — DarrylG
– DarrylG, Commented Apr 2, 2020 at 10:56
You will appreciate Python by seeing the above code can be written as: def twoNum(arr, t): return print(next(f"{i} + {j} = {t} " for i, j in zip(arr, arr) if i + j == t )). You won't get this by first thinking how would I program this in C++., but its okay to start learning but not good to submit such code for an interview. — DarrylG
– DarrylG, Commented Apr 2, 2020 at 11:03
I know it can be solved in linear time but I am just learning python for fun. So just want to try Brute force then efficient solution. Thank you for your help. — Nihal Mishra
– Nihal Mishra, Commented Apr 2, 2020 at 11:07

XPhyro · Accepted Answer · 2020-04-02 10:53:34Z

2

Change this:

def twoNum(*arr, t):

to this:

def twoNum(arr, t):

* is used to indicate that there will be a variable number of arguments, see this. It is not for pointers as in C++.

answered Apr 2, 2020 at 10:53

XPhyro

5481 gold badge7 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

NirO · Accepted Answer · 2020-04-02 10:58:34Z

0

Basically what you are trying to do is to write C code in python. I would instead try to focus first on how to write python code in a 'pythonic' way first. But for your question - sloving it your way using brute force in python:

In [173]: def two_num(arr, t):
 ...:     for i in arr:
 ...:         for j in arr[i + 1: ]:
 ...:             if i + j == t:
 ...:                 print(f"{i} + {j} = {t}")
 ...:                 return

answered Apr 2, 2020 at 10:58

NirO

2152 silver badges13 bronze badges

3 Comments

NirO Over a year ago

if you want the indices of i and j you can just return arr.index(i), arr.index(j)

NirO Over a year ago

If you want to solve it in a more efficient way you can sort the arr and then go from the edges inwards increment low whenever the sum < t and decrement high whenever sum > t

Nihal Mishra Over a year ago

I know it can be solved in linear time and in O(NlogN) using sorting but I am just learning python for fun. So just wanted to try Brute force then any other efficient solutions.

Alain T. · Accepted Answer · 2020-04-02 13:03:34Z

0

Here's a way to implement a brute force approach using a list comprehension:

arr = [1,3,5,7,9]
target = 6

i,j = next((i,j) for i,n in enumerate(arr[:-1]) for j,m in enumerate(arr[i+1:],i+1) if n+m==target)

output:

print(f"arr[{i}] + arr[{j}] = {arr[i]} + {arr[j]} = {target}")

# arr[0] + arr[2] = 1 + 5 = 6

Perhaps even more pythonic would be to use iterators:

from itertools import tee
iArr = enumerate(arr)
i,j  = next((i,j) for i,n in iArr for j,m in tee(iArr,1)[0] if n+m==target)

When you get to implementing an O(n) solution, you should look into dictionaries:

d   = { target-n:j for j,n in enumerate(arr) }
i,j = next( (i,d[m]) for i,m in enumerate(arr) if m in d and d[m] != i )

edited Apr 2, 2020 at 13:03

answered Apr 2, 2020 at 12:54

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Collectives™ on Stack Overflow

Two number Sum program in python O(N^2)

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related