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

Опубликовано: 26 Февраля, 2023

Учитывая массив arr[] различных элементов размером N , который отсортирован, а затем вокруг неизвестной точки, задача состоит в том, чтобы подсчитать количество пар в массиве, имеющих заданную сумму X .

Примеры:

Input: arr[] = {11, 15, 26, 38, 9, 10}, X = 35
Output: 1
Explanation: There is a pair (26, 9) with sum 35

Input: arr[] = {11, 15, 6, 7, 9, 10}, X = 16
Output: 2

Подход: Идея аналогична тому, что упомянуто ниже.

First find the largest element in an array which is the pivot point also and the element just after the largest is the smallest element. Once we have the indices of the largest and the smallest elements, we use a similar meet-in-middle algorithm (as discussed here in method 1) to count the number of pairs that sum up to X. Indices are incremented and decremented in a rotational manner using modular arithmetic.

Следуйте приведенной ниже иллюстрации для лучшего понимания.

Иллюстрация:

Let us take an example arr[]={11, 15, 6, 7, 9, 10}, X = 16, count=0;
Initially pivot = 1,  

l = 2, r = 1:
        => arr[2] + arr[1] = 6 + 15 = 21, which is > 16 
        => So decrement r = ( 6 + 1 – 1) % 6, r = 0

l = 2, r = 0:
        => arr[2] + arr[0] = 17 which is > 16,  
        => So decrement r = (6 + 0 – 1) % 6, r = 5

l = 2, r = 5:
        => arr[2] + arr[5] = 16 which is equal to 16,  
        => Hence count = 1 and
        => Decement r = (6 + 5 – 1) % 6, r = 4 and increment l = (2 + 1) % 6, l = 3

l = 3, r = 4:
        => arr[3] + arr[4] = 16
        => Hence increment count. So count = 2 
        => So decement r = (6 + 4 – 1) % 6, r = 3 and increment l = 4

l = 4, r = 3: 
        => l > r. So break the loop.

So we get count = 2

Для реализации идеи выполните следующие шаги:

  • Мы запустим цикл for от 0 до N-1 , чтобы узнать точку разворота . Установите левый указатель (l) на наименьшее значение и
    правый указатель (r) к самому высокому значению.
  • Чтобы ограничить круговое движение внутри массива, примените операцию по модулю на размер массива.
  • Пока л! = r , продолжайте проверять, если arr[l] + arr[r] = sum.
    • Если arr[l] + arr[r] > sum , обновить r=(N+r-1) % N .
    • Если arr[l] + arr[r] < sum , обновить l=(l+1) % N .
    • Если arr[l] + arr[r] = sum , увеличивается счетчик. Также увеличивайте l и уменьшайте r .

Ниже приведена реализация вышеизложенной идеи.

Временная сложность: O(N). Поскольку мы выполняем линейные операции над массивом.
Вспомогательное пространство: O(1). Поскольку используется постоянное дополнительное пространство.

Этот метод предложен Нихилом Джиндалом.

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