Skip to content

Instantly share code, notes, and snippets.

@pratik7368patil
Created July 16, 2020 11:52
Show Gist options
  • Save pratik7368patil/7e541b3db1cc23b629b52ba3efe9869c to your computer and use it in GitHub Desktop.
Save pratik7368patil/7e541b3db1cc23b629b52ba3efe9869c to your computer and use it in GitHub Desktop.
Four sum problem solution in Python (4sum)
def findFourElements(arr, N, K):
arr.sort()
for i in range(N - 3):
if i > 0 and arr[i] == arr[i-1]:
continue
for j in range(i+1, N - 2):
if j > i+1 and arr[j] == arr[j - 1]:
continue
l = j+1
r = N - 1
while(l < r):
sm = arr[i] + arr[j] + arr[l] + arr[r]
if sm == tar:
# here print all four elements
print(arr[i], arr[j], arr[l], arr[r])
while l < r and arr[l] == arr[l+1]:
l += 1
while l < r and arr[r] == arr[r-1]:
r -= 1
l += 1
r -= 1
elif sm < tar:
l += 1
else:
r -= 1
# here take required input
N, K = [int(v) for v in input().split()]
arr = [int(v) for v in input().split()]
findFourElements(arr, N, K)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment