Count pairs from a given array whose sum lies from a given range
Given an array arr[] consisting of N integers and two integers L and R, the task is to count the number of pairs whose sum lies in the range [L, R].
Examples:
Input: arr[] = {5, 1, 2}, L = 4, R = 7
Output: 2
Explanation:
The pairs satisfying the necessary conditions are as follows:
- (5, 1): Sum = 5 + 1 = 6, which lies in the range [4, 7].
- (5, 2): Sum = 5 + 2 = 7, which lies in the range [4, 7].
Therefore, the count of such pairs is 2.
Input: arr[] = {5, 1, 2, 4, 3}, L = 5, R = 8
Output: 7
Naive Approach: The simplest approach to solve the given problem is to generate all possible pairs and count those pairs whose sum lies over the range [L, R]. After checking for all the pairs, print the total count of pairs.
C++
#include <bits/stdc++.h> using namespace std; int countPairSum( int arr[], int L, int R, int N) { map< int , int > freq; // Counting frequency of each element for ( int i = 0; i < N; i++) freq[arr[i]]++; int count = 0; // Iterating through the array for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { if (arr[i] + arr[j] >= L && arr[i] + arr[j] <= R) { // check for duplicate if (arr[i] != arr[j]) { count += freq[arr[i]] * freq[arr[j]]; } else { count += (freq[arr[i]] * (freq[arr[i]] - 1)) / 2; } } } } // Return the value of count return count; } // Driver Code int main() { int arr[] = { 5, 1, 2, 4, 3 }; int L = 5, R = 8; int N = sizeof (arr) / sizeof (arr[0]); cout << countPairSum(arr, L, R, N); return 0; } // this code is contributed dany |
Java
// Java code for above approach import java.util.HashMap; class GFG { public static int countPairSum( int arr[], int L, int R, int N) { HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); // Counting frequency of each element for ( int i = 0 ; i < N; i++) { int key = arr[i]; if (freq.containsKey(key)) { freq.put(key, freq.get(key) + 1 ); } else { freq.put(key, 1 ); } } int count = 0 ; // Iterating through the array for ( int i = 0 ; i < N; i++) { for ( int j = i + 1 ; j < N; j++) { if (arr[i] + arr[j] >= L && arr[i] + arr[j] <= R) { // check for duplicate if (arr[i] != arr[j]) { count += freq.get(arr[i]) * freq.get(arr[j]); } else { count += (freq.get(arr[i]) * (freq.get(arr[i]) - 1 )) / 2 ; } } } } // Return the value of count return count; } // Driver Code public static void main(String[] args) { int arr[] = { 5 , 1 , 2 , 4 , 3 }; int L = 5 , R = 8 ; int N = arr.length; System.out.println(countPairSum(arr, L, R, N)); } } // This code is contributed by Pushpesh Raj. |
Python3
def count_pair_sum(arr, L, R, N): freq = {} # Counting frequency of each element for i in range (N): if arr[i] in freq: freq[arr[i]] + = 1 else : freq[arr[i]] = 1 count = 0 # Iterating through the array for i in range (N): for j in range (i + 1 , N): if arr[i] + arr[j] > = L and arr[i] + arr[j] < = R: # check for duplicate if arr[i] ! = arr[j]: count + = freq[arr[i]] * freq[arr[j]] else : count + = (freq[arr[i]] * (freq[arr[i]] - 1 )) / / 2 # Return the value of count return count # Driver Code #{5, 1, 2}, L = 4, R = 7 arr = [ 5 , 1 , 2 , 4 , 3 ] L = 5 R = 8 N = len (arr) print (count_pair_sum(arr, L, R, N)) # Contributed By Aditya Sharma |
C#
using System; using System.Collections.Generic; class GFG { public static int CountPairSum( int [] arr, int L, int R, int N) { Dictionary< int , int > freq = new Dictionary< int , int >(); // Counting frequency of each element for ( int i = 0; i < N; i++) { int key = arr[i]; if (freq.ContainsKey(key)) { freq[key]++; } else { freq[key] = 1; } } int count = 0; // Iterating through the array for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { if (arr[i] + arr[j] >= L && arr[i] + arr[j] <= R) { // check for duplicate if (arr[i] != arr[j]) { count += freq[arr[i]] * freq[arr[j]]; } else { count += (freq[arr[i]] * (freq[arr[i]] - 1)) / 2; } } } } // Return the value of count return count; } // Driver Code static void Main( string [] args) { int [] arr = { 5, 1, 2, 4, 3 }; int L = 5, R = 8; int N = arr.Length; Console.WriteLine(CountPairSum(arr, L, R, N)); } } |
Javascript
// Function to count pairs having sum in the range [L, R] from a given array function countPairSum(arr, L, R, N) { let freq = {}; // Counting frequency of each element for (let i = 0; i < N; i++) { if (freq[arr[i]]) { freq[arr[i]] += 1; } else { freq[arr[i]] = 1; } } let count = 0; // Iterating through the array for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { if (arr[i] + arr[j] >= L && arr[i] + arr[j] <= R) { // check for duplicate if (arr[i] != arr[j]) { count += freq[arr[i]] * freq[arr[j]]; } else { count += (freq[arr[i]] * (freq[arr[i]] - 1)) / 2; } } } } // Return the value of count return count; } // Driver Code let arr = [5, 1, 2, 4, 3]; let L = 5; let R = 8; let N = arr.length; console.log(countPairSum(arr, L, R, N)); |
7
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by sorting the array then performing a Binary Search to find the number of elements for each array element arr[i] such that the sum will not exceed the given range. Follow the steps to solve the problem:
- Sort the array arr[] in increasing order.
- Initialize variables say, right as N – 1 and count as 0 to store numbers of pairs whose sum lies over the range [L, R].
- Iterate until the right is greater than 0 and perform the following steps:
- Find the starting index of the element whose sum with arr[right] is greater than or equal to L, and store it in a variable, say start.
- Find the ending index of the element before arr[right] whose sum with arr[right] is less than or equal to R, and then store it in a variable, say end.
- If the end is greater than equal to the start, then add (end – start + 1) to the count representing the number of elements whose sum with the current element lies over the range [L, R] and then decrement right by 1.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count pairs whose // sum lies over the range [L, R] int countPairSum( int arr[], int L, int R, int N) { // Sort the given array sort(arr, arr + N); int right = N - 1, count = 0; // Iterate until right > 0 while (right > 0) { // Starting index of element // whose sum with arr[right] >= L auto it1 = lower_bound(arr, arr + N, L - arr[right]); int start = it1 - arr; // Ending index of element // whose sum with arr[right] <= R auto it2 = upper_bound(arr, arr + N, R - arr[right]); --it2; int end = it2 - arr; // Update the value of end end = min(end, right - 1); // Add the count of elements // to the variable count if (end - start >= 0) { count += (end - start + 1); } right--; } // Return the value of count return count; } // Driver Code int main() { int arr[] = { 5, 1, 2, 4, 3 }; int L = 5, R = 8; int N = sizeof (arr) / sizeof (arr[0]); cout << countPairSum(arr, L, R, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static int lowerBound( int [] a, int low, int high, int element){ while (low < high){ int middle = low + (high - low)/ 2 ; if (element > a[middle]) low = middle + 1 ; else high = middle; } return low; } static int upperBound( int [] a, int low, int high, int element){ while (low < high){ int middle = low + (high - low)/ 2 ; if (a[middle] > element) high = middle; else low = middle + 1 ; } return low; } // Function to count pairs whose // sum lies over the range [L, R] static int countPairSum( int arr[], int L, int R, int N) { // Sort the given array Arrays.sort(arr); int right = N - 1 , count = 0 ; // Iterate until right > 0 while (right > 0 ) { // Starting index of element // whose sum with arr[right] >= L int it1 = lowerBound(arr, 0 ,N, L - arr[right]); it1++; int start = it1 - arr[ 0 ]; // Ending index of element // whose sum with arr[right] <= R int it2 = upperBound(arr, 0 ,N, R - arr[right]); int end = it2 - arr[ 0 ]; // Update the value of end end = Math.min(end, right - 1 ); // Add the count of elements // to the variable count if (end - start >= 0 ) { count += (end - start + 1 ); } right--; } // Return the value of count return count; } // Driver Code public static void main(String[] args) { int arr[] = { 5 , 1 , 2 , 4 , 3 }; int L = 5 , R = 8 ; int N = arr.length; System.out.print(countPairSum(arr, L, R, N)); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach from bisect import bisect_left, bisect_right # Function to count pairs whose # sum lies over the range [L, R] def countPairSum(arr, L, R, N): # Sort the given array arr.sort() right = N - 1 count = 0 # Iterate until right > 0 while (right > 0 ): # Starting index of element # whose sum with arr[right] >= L it1 = bisect_left(arr, L - arr[right]) start = it1 # Ending index of element # whose sum with arr[right] <= R it2 = bisect_right(arr, R - arr[right]) it2 - = 1 end = it2 # Update the value of end end = min (end, right - 1 ) # Add the count of elements # to the variable count if (end - start > = 0 ): count + = (end - start + 1 ) right - = 1 # Return the value of count return count # Driver Code if __name__ = = '__main__' : arr = [ 5 , 1 , 2 , 4 , 3 ] L = 5 R = 8 N = len (arr) print (countPairSum(arr, L, R, N)) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approach using System; public class GFG { static int lowerBound( int [] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low; } static int upperBound( int [] a, int low, int high, int element) { while (low < high) { int middle = low + (high - low) / 2; if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Function to count pairs whose // sum lies over the range [L, R] static int countPairSum( int []arr, int L, int R, int N) { // Sort the given array Array.Sort(arr); int right = N - 1, count = 0; // Iterate until right > 0 while (right > 0) { // Starting index of element // whose sum with arr[right] >= L int it1 = lowerBound(arr, 0, N, L - arr[right]); it1++; int start = it1 - arr[0]; // Ending index of element // whose sum with arr[right] <= R int it2 = upperBound(arr, 0, N, R - arr[right]); int end = it2 - arr[0]; // Update the value of end end = Math.Min(end, right - 1); // Add the count of elements // to the variable count if (end - start >= 0) { count += (end - start + 1); } right--; } // Return the value of count return count; } // Driver Code public static void Main(String[] args) { int []arr = { 5, 1, 2, 4, 3 }; int L = 5, R = 8; int N = arr.Length; Console.Write(countPairSum(arr, L, R, N)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // javascript program for the above approach function lowerBound(a , low , high , element) { while (low < high) { var middle = low + parseInt((high - low) / 2); if (element > a[middle]) low = middle + 1; else high = middle; } return low; } function upperBound(a , low , high , element) { while (low < high) { var middle = low + parseInt((high - low) / 2); if (a[middle] > element) high = middle; else low = middle + 1; } return low; } // Function to count pairs whose // sum lies over the range [L, R] function countPairSum(arr , L , R , N) { // Sort the given array arr.sort((a,b)=>a-b); var right = N - 1, count = 0; // Iterate until right > 0 while (right > 0) { // Starting index of element // whose sum with arr[right] >= L var it1 = lowerBound(arr, 0, N, L - arr[right]); it1++; var start = it1 - arr[0]; // Ending index of element // whose sum with arr[right] <= R var it2 = upperBound(arr, 0, N, R - arr[right]); var end = it2 - arr[0]; // Update the value of end end = Math.min(end, right - 1); // Add the count of elements // to the variable count if (end - start >= 0) { count += (end - start + 1); } right--; } // Return the value of count return count; } // Driver Code var arr = [ 5, 1, 2, 4, 3 ]; var L = 5, R = 8; var N = arr.length; document.write(countPairSum(arr, L, R, N)); // This code is contributed by gauravrajput1 </script> |
7
Time Complexity: O(N*log N)
Auxiliary Space: O(1)