Given an array arr[] of N integers, the task is to count the number of pairs with positive sum.
Examples:
Input: arr[] = {-7, -1, 3, 2}
Output: 3
Explanation:
The pairs with positive sum are: {-1, 3}, {-1, 2}, {3, 2}.Input: arr[] = {-4, -2, 5}
Output: 2
Explanation:
The pairs with positive sum are: {-4, 5}, {-2, 5}.
Naive Approach:
A naive approach is to traverse each element and check if there is another number in the array arr[] which can be added to it to give the positive-sum or not.
Below is the implementation of the above approach:
C++
// Naive approach to count pairs // with positive sum. #include <bits/stdc++.h> using namespace std;   // Returns number of pairs in // arr[0..n-1] with positive sum int CountPairs(int arr[], int n) {     // Initialize result     int count = 0;       // Consider all possible pairs     // and check their sums     for (int i = 0; i < n; i++) {         for (int j = i + 1; j < n; j++) {               // If arr[i] & arr[j]             // form valid pair             if (arr[i] + arr[j] > 0)                 count += 1;         }     }       return count; }   // Driver's Code int main() {     int arr[] = { -7, -1, 3, 2 };     int n = sizeof(arr) / sizeof(arr[0]);       // Function call to find the     // count of pairs     cout << CountPairs(arr, n);     return 0; } |
Java
// Java implementation of the above approach class GFG {               // Naive approach to count pairs     // with positive sum.           // Returns number of pairs in     // arr[0..n-1] with positive sum     static int CountPairs(int arr[], int n)     {         // Initialize result         int count = 0;               // Consider all possible pairs         // and check their sums         for (int i = 0; i < n; i++) {             for (int j = i + 1; j < n; j++) {                       // If arr[i] & arr[j]                 // form valid pair                 if (arr[i] + arr[j] > 0)                     count += 1;             }         }               return count;     }           // Driver's Code     public static void main (String[] args)     {         int []arr = { -7, -1, 3, 2 };         int n = arr.length;               // Function call to find the         // count of pairs         System.out.println(CountPairs(arr, n));     } }   // This code is contributed by Yash_R |
Python3
# Naive approach to count pairs # with positive sum.   # Returns number of pairs in # arr[0..n-1] with positive sum def CountPairs(arr, n) :     # Initialize result     count = 0;       # Consider all possible pairs     # and check their sums     for i in range(n) :         for j in range( i + 1, n) :               # If arr[i] & arr[j]             # form valid pair             if (arr[i] + arr[j] > 0) :                 count += 1;       return count;   # Driver's Code if __name__ == "__main__" :       arr = [ -7, -1, 3, 2 ];     n = len(arr);       # Function call to find the     # count of pairs     print(CountPairs(arr, n));       # This code is contributed by Yash_R |
Output:
3
Time Complexity: O(N2)
Efficient Approach:
The idea is to use the Two Pointers Technique. Following are the steps:
- Sort the given array arr[] in increasing order.
- Take two pointers. one representing the first element and second representing the last element of the sorted array.
- If the sum of elements at these pointers is greater than 0, then the difference between the pointers will give the count of pairs with positive-sum for the element at second pointers. Decrease the second pointer by 1.
- Else increase the first pointers by 1.
- Repeat the above steps untill both pointers converge towards each other.
Below is the implementation of the above approach:
C++
// C++ program to count the // pairs with positive sum #include <bits/stdc++.h> using namespace std;   // Returns number of pairs // in arr[0..n-1] with // positive sum int CountPairs(int arr[], int n) {     // Sort the array in     // increasing order     sort(arr, arr + n);       // Intialise result     int count = 0;       // Intialise first and     // second pointer     int l = 0, r = n - 1;       // Till the pointers     // doesn't converge     // traverse array to     // count the pairs     while (l < r) {           // If sum of arr[i] &&         // arr[j] > 0, then the         // count of pairs with         // positive sum is the         // difference between         // the two pointers         if (arr[l] + arr[r] > 0) {               // Increase the count             count += (r - l);             r--;         }         else {             l++;         }     }     return count; }   // Driver's Code int main() {     int arr[] = { -7, -1, 3, 2 };     int n = sizeof(arr) / sizeof(arr[0]);       // Function call to count     // the pairs with positive     // sum     cout << CountPairs(arr, n);     return 0; } |
Python3
# Python3 program to count the # pairs with positive sum   # Returns number of pairs # in arr[0..n-1] with # positive sum def CountPairs(arr, n) :       # Sort the array in     # increasing order     arr.sort()       # Intialise result     count = 0;       # Intialise first and     # second pointer     l = 0; r = n - 1;       # Till the pointers     # doesn't converge     # traverse array to     # count the pairs     while (l < r) :           # If sum of arr[i] &&         # arr[j] > 0, then the         # count of pairs with         # positive sum is the         # difference between         # the two pointers         if (arr[l] + arr[r] > 0) :               # Increase the count             count += (r - l);             r -= 1;                   else :             l += 1;                   return count;   # Driver's Code if __name__ == "__main__" :       arr = [ -7, -1, 3, 2 ];     n = len(arr);       # Function call to count     # the pairs with positive     # sum     print(CountPairs(arr, n));   # This code is contributed by Yash_R |
Output:
3
Time Complexity: O(N*log N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/count-number-of-pairs-with-positive-sum-in-an-array/ […]
… [Trackback]
[…] Here you can find 34110 additional Info to that Topic: geeksforgeeks.org/count-number-of-pairs-with-positive-sum-in-an-array/ […]