Problem link - Count Pairs
Problem Statement:
Given a sorted array of integers and a value X, count the number of pairs (i, j) such that i < j and the sum of arr[i] + arr[j] is less than X.
Approach:
The key idea to solve this problem is to use a two-pointer technique on the sorted array to efficiently count the pairs. We initialize two pointers: one at the start of the array (left) and the other at the end (right). By checking the sum of the elements at these pointers, we can determine if it is less than X. If it is, all elements between the left and right pointers also form valid pairs with the element at the left pointer, so we count those pairs and move the left pointer to the right. If the sum is not less than X, we move the right pointer to the left to try and reduce the sum. We repeat this process until the left pointer meets the right pointer.
Time Complexity:
O(n log n), where n is the number of elements in the array due to the sorting step.
Space Complexity:
O(1), as we are using a constant amount of extra space for the pointers.