Рубрики

Подсчет пар в отсортированном массиве, сумма которого меньше x

Учитывая отсортированный массив целых чисел и число x, задача состоит в том, чтобы подсчитать пары в массиве, сумма которых меньше x.

Примеры:

Input  : arr[] = {1, 3, 7, 9, 10, 11}
         x = 7
Output : 1
There is only one pair (1, 3)

Input  : arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
         x = 7
Output : 6
Pairs are (1, 2), (1, 3), (1, 4), (1, 5)
          (2, 3) and (2, 4)  

Простое решение этой проблемы — запустить два цикла, чтобы сгенерировать все пары и одну за другой, и проверить, меньше ли сумма текущей пары, чем x, или нет.

Эффективным решением этой проблемы является получение начального и последнего значения индекса в переменных l и r.

1) Initialize two variables l and r to find the candidate 
   elements in the sorted array.
       (a) l = 0
       (b) r = n - 1
2) Initialize : result = 0
2) Loop while l < r.

    // If current left and current
    // right have sum smaller than x,
    // the all elements from l+1 to r
    // form a pair with current
    (a) If (arr[l] + arr[r] < x)  
          result = result + (r - l)      
   
    (b) Else
            r--;
       
3) Return result

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

C ++

// C ++ программа для подсчета пар в массиве
// чья сумма меньше заданного числа x
#include<bits/stdc++.h>

using namespace std;

  
// Функция для подсчета пар в массиве
// с суммой меньше х.

int findPairs(int arr[],int n,int x)

{

    int l = 0, r = n-1;

    int result = 0;

  

    while (l < r)

    {

        // Если текущий слева и текущий

        // справа есть сумма меньше x,

        // все элементы от l + 1 до r

        // формируем пару с текущим l.

        if (arr[l] + arr[r] < x)

        {

            result += (r - l);

            l++;

        }

  

        // Перейти к меньшему значению

        else

            r--;

    }

  

    return result;

}

  
// Управляемый код

int main()

{

    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};

    int n = sizeof(arr)/sizeof(int);

    int x = 7;

    cout << findPairs(arr, n, x);

    return 0;

}

Джава

// Java-программа для подсчета пар в массиве
// чья сумма меньше заданного числа x

class GFG {

      

    // Функция для подсчета пар в массиве

    // с суммой меньше х.

    static int findPairs(int arr[], int n, int x)

    {

          

        int l = 0, r = n - 1;

        int result = 0;

      

        while (l < r)

        {

              

            // Если текущий слева и текущий

            // справа есть сумма меньше x,

            // все элементы от l + 1 до r

            // формируем пару с текущим l.

            if (arr[l] + arr[r] < x)

            {

                result += (r - l);

                l++;

            }

      

            // Перейти к меньшему значению

            else

                r--;

        }

      

        return result;

    }

      

    // Метод драйвера

    public static void main(String[] args)

    {

          

        int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};

        int n = arr.length;

        int x = 7;

          

        System.out.print(findPairs(arr, n, x));

    }

}

  
// Этот код предоставлен Anant Agarwal.

python3

# Python3 программа для подсчета пар
# в массиве с меньшей суммой
# чем задано число х

  
# Функция для подсчета пар в массиве
# с суммой меньше х.

def findPairs(arr, n, x):

  

    l = 0; r = n-1

    result = 0

  

    while (l < r):

      

        # Если текущий левый и текущий

        # справа есть сумма, меньшая х,

        # все элементы от l + 1 до r

        # сформировать пару с текущим l.

        if (arr[l] + arr[r] < x):

          

            result += (r - l)

            l += 1

          

  

        # Перейти к меньшему значению

        else:

            r -= 1

  

    return result

      
Код водителя

arr = [1, 2, 3, 4, 5, 6, 7, 8]

n = len(arr)

x = 7

print(findPairs(arr, n, x))

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для подсчета пар в
// массив с меньшей суммой
// чем задано число х

using System;

  

class GFG {

      

    // Функция для подсчета пар в массиве

    // с суммой меньше х.

    static int findPairs(int []arr, int n,

                         int x)

    {

          

        int l = 0, r = n - 1;

        int result = 0;

      

        while (l < r)

        {

              

            // Если текущий слева и текущий

            // справа есть сумма меньше x,

            // все элементы от l + 1 до r

            // формируем пару с текущим l.

            if (arr[l] + arr[r] < x)

            {

                result += (r - l);

                l++;

            }

      

            // Перейти к меньшему значению

            else

                r--;

        }

      

        return result;

    }

      

    // Код драйвера

    public static void Main(String[] args)

    {

          

        int []arr = {1, 2, 3, 4, 5, 6, 7, 8};

        int n = arr.Length;

        int x = 7;

          

        Console.Write(findPairs(arr, n, x));

    }

}

  
// Этот код предоставлен parashar ...

PHP

<?php
// PHP программа для подсчета пар в массиве
// чья сумма меньше заданного числа x

  
// Функция для подсчета пар в массиве
// с суммой меньше х.

function findPairs($arr,$n,$x)

{

    $l = 0; 

    $r = $n - 1;

    $result = 0;

  

    while ($l < $r)

    {

          

        // Если текущий слева и текущий

        // справа есть сумма меньше x,

        // все элементы от l + 1 до r

        // формируем пару с текущим l.

        if ($arr[$l] + $arr[$r] < $x)

        {

            $result += ($r - $l);

            $l++;

        }

  

        // Перейти к меньшему значению

        else

            $r--;

    }

  

    return $result;

}

  

    // Код драйвера

    $arr = array(1, 2, 3, 4, 5, 6, 7, 8);

    $n = sizeof($arr) / sizeof($arr[0]);

    $x = 7;

    echo findPairs($arr, $n, $x);

    return 0;

  
// Этот код предоставлен нитин митталь.
?>


Выход:

6

Временная сложность: O (n)
Пространство сложность: O (1)

Расширение:
Если массив не отсортирован, то мы можем сначала отсортировать массив, а затем применить указанный выше метод для решения за O (n Log n) времени.

Статьи по Теме:
Подсчитайте все разные пары с разностью, равной k
Подсчитать пары с заданной суммой

Ссылка: https://www.quora.com/Given-a-sorted-integer-array-and-number-z-count-all-pairs-xy-in-the-array-so-that-x-+- уг-Can-это будет сделано в-On

Эта статья предоставлена DANISH_RAZA . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Подсчет пар в отсортированном массиве, сумма которого меньше x

0.00 (0%) 0 votes