Skip to content

Instantly share code, notes, and snippets.

@rakshitraj
Last active August 6, 2020 08:00
Show Gist options
  • Save rakshitraj/43f4b51997556b88b4cae78e39449c76 to your computer and use it in GitHub Desktop.
Save rakshitraj/43f4b51997556b88b4cae78e39449c76 to your computer and use it in GitHub Desktop.
Counting pais with difference
def sort(array):
"""Sort the array by using quicksort."""
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
# Removing non-unique elememts
m = [pivot]
return sort(less)+m+sort(greater)
else:
return array
# A sorting based program to
# count pairs with difference k
def countPairsWithDiffK(numbers,k):
count =0
# Sort array elements
arr = sort(numbers)
# pointer left
l =0
# pointer right
r=0
while r<(len(arr)):
if arr[r]-arr[l]==k:
count+=1
l+=1
r+=1
elif arr[r]-arr[l]>k:
l+=1
else:
r+=1
return count
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment