Count number of pairs with positive sum in an array
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 |
C#
// C# implementation of the above approach using System; class GFG { // Naive approach to count pairs with positive sum. // Returns the number of pairs in arr[0..n-1] with a // 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] and arr[j] form a 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 Console.WriteLine(CountPairs(arr, n)); } } |
Javascript
function CountPairs(arr, n) { // Initialize the result let count = 0; // Consider all possible pairs and check their sums for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { // If arr[i] and arr[j] form a valid pair if (arr[i] + arr[j] > 0) { count++; } } } return count; } // Driver's Code const arr = [-7, -1, 3, 2]; const n = arr.length; // Function call to find the count of pairs console.log(CountPairs(arr, n)); |
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The idea is to use the Two Pointers Technique
Step-by-step approach:
- 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; } |
Java
import java.util.Arrays; public class Main { // Returns the number of pairs in arr[0..n-1] with a positive sum static int countPairs( int arr[], int n) { // Sort the array in increasing order Arrays.sort(arr); // Initialize result int count = 0 ; // Initialize first and second pointers int l = 0 , r = n - 1 ; // Traverse the array to count the pairs until the pointers converge while (l < r) { // If the sum of arr[i] and 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 public static void main(String[] args) { int arr[] = { - 7 , - 1 , 3 , 2 }; int n = arr.length; // Function call to count the pairs with positive sum System.out.println(countPairs(arr, n)); } } |
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 |
C#
using System; class GFG { public static int countPairs( int [] arr) { // Sort the array in increasing order Array.Sort(arr); // Initialize the result int count = 0; // Initialize the left and right pointers int l = 0; int r = arr.Length - 1; // Traverse the array to count the pairs while (l < r) { // If the sum of arr[i] and arr[j] > 0, // then the count of pairs with a positive sum // is the difference between the two pointers if (arr[l] + arr[r] > 0) { count += r - l; r--; } else { l++; } } return count; } public static void Main( string [] args) { // Example usage: int [] arr = new int [] { -7, -1, 3, 2 }; int result = countPairs(arr); Console.WriteLine(result); } } |
Javascript
function countPairs(arr) { // Sort the array in increasing order arr.sort((a, b) => a - b); // Initialize the result let count = 0; // Initialize the left and right pointers let l = 0; let r = arr.length - 1; // Traverse the array to count the pairs while (l < r) { // If the sum of arr[i] and arr[j] > 0, // then the count of pairs with a positive sum // is the difference between the two pointers if (arr[l] + arr[r] > 0) { count += r - l; r--; } else { l++; } } return count; } // Example usage: const arr = [-7, -1, 3, 2]; const result = countPairs(arr); console.log(result); |
3
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Contact Us