Количество пар элементов массива со средним значением не менее K

Опубликовано: 19 Сентября, 2022

Дан массив A[] размера N , состоящий из N целых чисел, задача состоит в том, чтобы подсчитать количество пар, среднее значение которых больше или равно K.

Пример:

Input: N = 4, K = 3, A = {5, 1, 3, 4}
Output: 4
Explanation: (5, 1), (5, 3), (5, 4) and (3, 4) are the required pairs with average greater or equal to K = 3.

Input: N = 3, K = 3, A = {1, 2, 3}
Output: 0
Explanation: No pairs exist with average greater or equal to K = 3.

Подход: Эту проблему можно решить с помощью бинарного поиска первого вхождения элемента в на основе следующего наблюдения:

  • Just need to find 2*K – A[i] because average of two numbers X and Y is K ≤ (X+Y)/2. Now replace X with the current element that we are traversing i.e A[i] then equation becomes Y ≥ 2*K-A[i].
  • So for any element A[i] in the array A[] total number of pairs formed are all the numbers in A[] that are greater than or equal to 2*K-A[i] i.e size of array ‘A’ -index of 2*K-A[i].
  • So go as left as possible in A[] and for that find the first occurrence of 2*K-A[i]. If 2*K-A[i] is not found in A[] then return the index of next greater element of 2*K-A[i] because if average ≤ (X+Y)/2 for any two integers then also average ≤ (X+Z)/2 for all Z ≥ Y. 

Выполните следующие шаги, чтобы решить эту проблему:

  • Отсортируйте массив A[].
  • Пройдите массив A[] .
    • Найдите первое вхождение 2*kA[i] для каждого элемента А [я] в А.
    • Если 2*kA[i] не существует, найдите первое вхождение элемента чуть больше 2*kA[i] в массиве A и сохраните его результат в переменной (скажем, ind ).
    • Если инд не -1, затем добавьте в ответ N-ind .
  • Вернуть окончательный ответ после завершения обхода.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (N log N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ