Count Pairs with Smaller Sum
Given a sorted array of N distinct integers and an integer K, find the number of pairs of indices (i, j) such that i < j and the sum of the elements at these indices is strictly less than K (i.e., arr[i] + arr[j] < K).
Input
The first line contains two integers N and K, separated by a space. The second line contains N space-separated integers representing the sorted array arr. Assume N >= 1.
Output
Print a single integer representing the count of such pairs.
Constraints
1 <= N <= 1000. The elements of the array are distinct integers. The values of array elements and K are between -10^9 and 10^9.
Example 1
5 10 1 3 5 7 9
4
Pairs are (1,3), (1,5), (1,7), (1,9), (3,5), (3,7). Sums: 4, 6, 8, 10, 8, 10. Pairs with sum < 10: (1,3), (1,5), (1,7), (3,5). Count = 4.
Example 2
3 5 -2 1 4
2
Pairs are (-2,1), (-2,4), (1,4). Sums: -1, 2, 5. Pairs with sum < 5: (-2,1), (-2,4). Count = 2.
Hints
Similar problems
- Count Unique Element PairsMedium
- Count Distinct ElementsEasy
- Minimize Maximum Difference in PairsMedium
- Pairs with Same ParityMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Sort by Subsequence SumMedium
More topics: Hash Map and Hashing problems, Two Pointers problems, Sorting problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 10 1 3 5 7 9
3 5 -2 1 4