Cuente el número de pares con suma positiva en una array

Dada una array arr[] de N enteros, la tarea es contar el número de pares con suma positiva.

Ejemplos:

Entrada: arr[] = {-7, -1, 3, 2}
Salida: 3
Explicación:
Los pares con suma positiva son: {-1, 3}, {-1, 2}, {3, 2}.

Entrada: arr[] = {-4, -2, 5}
Salida: 2
Explicación:
Los pares con suma positiva son: {-4, 5}, {-2, 5}.

Enfoque ingenuo:
un enfoque ingenuo es atravesar cada elemento y verificar si hay otro número en la array arr[] que se pueda agregar para obtener la suma positiva o no.

A continuación se muestra la implementación del enfoque anterior:

// 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 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

# 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

3

Complejidad del tiempo: O(N ² )

Enfoque Eficiente:
La idea es utilizar la Técnica de los Dos Punteros . Los siguientes son los pasos:

1. Ordene la array dada arr[] en orden creciente.
2. Tome dos punteros. uno que representa el primer elemento y el segundo que representa el último elemento de la array ordenada .
3. Si la suma de los elementos en estos punteros es mayor que 0, la diferencia entre los punteros dará el recuento de pares con suma positiva para el elemento en los segundos punteros. Disminuya el segundo puntero en 1.
4. De lo contrario, aumente los primeros punteros en 1.
5. Repita los pasos anteriores hasta que ambos punteros converjan uno hacia el otro.

A continuación se muestra la implementación del enfoque anterior:

// 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 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

3

Complejidad de tiempo: O(N*log N)