CODEWITHSUNDEEP
pythonarraysalgorithm
Nihal Mishra
Nihal Mishra

Reputation: 1

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

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,

Upvotes: 0

Views: 551

Answers (3)

Alain T.
Alain T.

Reputation: 42139

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 )

Upvotes: 0

NirO
NirO

Reputation: 217

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

Upvotes: 0

XPhyro
XPhyro

Reputation: 528

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

Upvotes: 2

Related Questions