Given an array of numbers, Count the number of pairs with sum less than or equal to K
For example consider the array {5, 1, 12, 3, 6},
pairs with sum <= 10 are {(1,3), (1,5), (1,6), (3,5), (3,6)}.
So there are 5 pairs with the given constraint.
In one of the previous posts, we have seen how to find a pair with given sum in the given array. This problem is a variation of that.
Let us look at the algorithm.
- First sort the array in ascending order.
- Take two indices one(b) pointing to the start of the array, and the other(e) pointing to the last element of the array.
- If A[b]+A[e] <= K
- A[b] + A[i] <= K for b < i < e. Hence (e-b) elements satisfy the given property.
- Increment b and decrement e and repeat step 3
- Otherwise decrement e
- Repeat step 3 until b and e meet each other.
A[0] A[1] A[2]… A[N]
b–> <–e
Considering the above example
{1, 3, 5, 6, 12} let b = 0, e = 3 and K = 10
If we add 6 or 5 or 3 to 1, the sum is less than 10. At this point, we can increment the pair count in one shot.
1 3 5 6 12
b e
If we add 6 or 5 or 3 to 1, the sum is less than 10. At this point, we can increment the pair count in one shot.
Here is Java implementation of the above algorithm. This solution runs in O(n log n).