Given an array of integers find the number of all ordered pairs of elements in the array whose sum lies in a given range [a,b]
Here is an O(n^2) solution for the same
'''
counts all pairs in array such that the
sum of pair lies in the range a and b
'''
def countpairs(array, a, b):
num_of_pairs = 0
for i in range(len(array)):
for j in range(i+1,len(array)):
total = array[i] + array[j]
if total >= a and total <= b:
num_of_pairs += 1
return num_of_pairs
I know my solution is not optimal What is a better algorithm for doing this.
The time complexity is of course output-sensitive, but this is still superior to the existing algo:
O(nlogn) + O(k)
where k is the number of pairs that satisfy the condition.
Note: If you only need to count the number of pairs, you can do it in O(nlogn). Modify the above algorithm so [b - x] (or the next smaller element) is also searched for. This way, you can count the number of 'matches' each element has in O(logn) simply from the indices of the first and last match. Then it's just a question of summing those up to get the final count. This way, the initial O(nlogn) sorting step is dominant.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments