Recuento de pares de elementos Array con un promedio de al menos K

Dada una array A[] de tamaño N que consta de N enteros, la tarea es contar el número de pares tales que su promedio sea mayor o igual a K.

Ejemplo:

Entrada: N = 4, K = 3, A = {5, 1, 3, 4}
Salida: 4
Explicación: (5, 1), (5, 3), (5, 4) y (3, 4) son los pares requeridos con promedio mayor o igual a K = 3.

Entrada: N = 3, K = 3, A = {1, 2, 3}
Salida: 0
Explicación: No existen pares con promedio mayor o igual a K = 3.

Acercarse:Este problema se puede resolver mediante la búsqueda binaria de la primera aparición de un elemento en función de la siguiente observación:

• Solo necesito encontrar 2*K – A[i] porque el promedio de dos números X e Y es K ≤ (X+Y)/2. Ahora reemplace X con el elemento actual que estamos atravesando, es decir, A[i], luego la ecuación se convierte en Y ≥ 2*KA[i].
• Entonces, para cualquier elemento A[i] en la array A[], el número total de pares formados son todos los números en A[] que son mayores o iguales a 2*KA[i]es decir, el tamaño de la array ‘A’ -índice de 2 *KA[yo] .
• Así que ve lo más a la izquierda posible en A[] y para eso encuentra la primera ocurrencia de 2*KA[i]. Si 2*KA[i] no se encuentra en A[] , devuelva el índice del siguiente elemento mayor de 2*KA[i] porque si el promedio ≤ (X+Y)/2 para dos enteros cualquiera, entonces también el promedio ≤ (X+ Z)/2 para todo Z ≥ Y. 

Siga los pasos a continuación para resolver este problema: 

• Ordene la array A[].
• Atraviesa la array A[] .
  • Encuentre la primera ocurrencia de 2*kA[i]para cada elementoA[i] en A. 
  • Si 2*kA[i] no existe, busque la primera aparición de un elemento justo mayor que 2*kA[i] en la array A y almacene su resultado en una variable (por ejemplo, ind ).
  •  Si ind no es-1, agregue N-ind en la respuesta.
•  Devuelve la respuesta final después de que finaliza el recorrido.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the index of 2*K-A[i]
int findElement(int A[], int low,
                int high, int key)
{
    int ans = -1;
 
    // Binary search
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (key <= A[mid]) {
            ans = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
    return ans;
}
 
// Count the number of pairs
int countPairs(int A[], int& N, int& k)
{
    sort(A, A + N);
    int count = 0;
 
    // Loop to count the number of pairs
    for (int i = 0; i < N; i++) {
        int index
            = findElement(A, i + 1, N - 1,
                          2 * k - A[i]);
        if (index != -1)
            count += N - index;
    }
    return count;
}
 
// Driver Code
int main()
{
    int A[] = { 5, 1, 3, 4 };
    int N = sizeof(A) / sizeof(A[0]);
    int K = 3;
 
    // Function call
    cout << countPairs(A, N, K);
    return 0;
}

// Java code to implement the approach
import java.util.*;
 
class GFG {   
 
  // Function to return the index of 2*K-A[i]
  static int findElement(int A[], int low,
                         int high, int key)
  {
    int ans = -1;
 
    // Binary search
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (key <= A[mid]) {
        ans = mid;
        high = mid - 1;
      }
      else
        low = mid + 1;
    }
    return ans;
  }
 
  // Count the number of pairs
  static int countPairs(int A[], int N, int k)
  {
    Arrays.sort(A);
    int count = 0;
 
    // Loop to count the number of pairs
    for (int i = 0; i < N; i++) {
      int index
        = findElement(A, i + 1, N - 1,
                      2 * k - A[i]);
      if (index != -1)
        count += N - index;
    }
    return count;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int A[] = { 5, 1, 3, 4 };
    int N = A.length;
    int K = 3;
 
    // Function call
    System.out.print(countPairs(A, N, K));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python3 program for above approach
 
# Function to return the index of 2*K-A[i]
def findElement(A, low, high, key):
    ans = -1
 
    # binary search
    while (low <= high):
        mid = low + (high - low)//2
        if key <= A[mid]:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans
 
# Count the number of pairs
def countPairs(A, N, k):
    A.sort()
    count = 0
     
    # Loop to count the number of pairs
    for i in range(N):
        index = findElement(A, i + 1, N - 1, 2 * k - A[i])
        if index != -1:
            count += N - index
    return count
 
# Driver code
A = [5, 1, 3, 4]
N = len(A)
K = 3
 
# Function call
print(countPairs(A, N, K))
 
# this code is contributed by phasing17

// C# code to implement the approach
using System;
 
public class GFG {
    // Function to return the index of 2*K-A[i]
    static int findElement(int[] A, int low, int high,
                           int key)
    {
        int ans = -1;
 
        // Binary search
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (key <= A[mid]) {
                ans = mid;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
        return ans;
    }
 
    // Count the number of pairs
    static int countPairs(int[] A, int N, int k)
    {
        Array.Sort(A);
        int count = 0;
 
        // Loop to count the number of pairs
        for (int i = 0; i < N; i++) {
            int index = findElement(A, i + 1, N - 1,
                                    2 * k - A[i]);
            if (index != -1)
                count += N - index;
        }
        return count;
    }
 
    // Driver Code
    static public void Main()
    {
        int[] A = { 5, 1, 3, 4 };
        int N = A.Length;
        int K = 3;
 
        // Function call
        Console.Write(countPairs(A, N, K));
    }
}
 
// This code is contributed by Rohit Pradhan

<script>
      // JavaScript code for the above approach
 
      // Function to return the index of 2*K-A[i]
      function findElement(A, low,
          high, key) {
          let ans = -1;
 
          // Binary search
          while (low <= high) {
              let mid = low + Math.floor((high - low) / 2);
              if (key <= A[mid]) {
                  ans = mid;
                  high = mid - 1;
              }
              else
                  low = mid + 1;
          }
          return ans;
      }
 
      // Count the number of pairs
      function countPairs(A, N, k) {
          A.sort(function (a, b) { return a - b });
          let count = 0;
 
          // Loop to count the number of pairs
          for (let i = 0; i < N; i++) {
              let index
                  = findElement(A, i + 1, N - 1,
                      2 * k - A[i]);
              if (index != -1)
                  count += N - index;
          }
          return count;
      }
 
      // Driver Code
      let A = [5, 1, 3, 4];
      let N = A.length;
      let K = 3;
 
      // Function call
      document.write(countPairs(A, N, K));
 
  // This code is contributed by Potta Lokesh
  </script>

4

Complejidad temporal: O(N log N) 
Espacio auxiliar: O(N)