Рубрики

Учитывая массив A [] и число x, проверьте на пару в A [] с суммой как x

Напишите программу, которая, учитывая массив A [] из n чисел и другого числа x, определяет, существуют ли в S два элемента, сумма которых равна точно x.

МЕТОД 1 (Использовать сортировку)

Алгоритм:

hasArrayTwoCandidates (A[], ar_size, sum)
1) Sort the array in non-decreasing order.
2) Initialize two index variables to find the candidate 
   elements in the sorted array.
       (a) Initialize first to the leftmost index: l = 0
       (b) Initialize second  the rightmost index:  r = ar_size-1
3) Loop while l < r.
       (a) If (A[l] + A[r] == sum)  then return 1
       (b) Else if( A[l] + A[r] <  sum )  then l++
       (c) Else r--    
4) No candidates in whole array - return 0

Сложность времени: зависит от того, какой алгоритм сортировки мы используем. Если мы используем Merge Sort или Heap Sort, то (-) (nlogn) в худшем случае. Если мы используем быструю сортировку, то O (n ^ 2) в худшем случае.
Вспомогательное пространство: опять же, зависит от алгоритма сортировки. Например, вспомогательная область O (n) для сортировки слиянием и O (1) для сортировки кучи.

Пример :

Пусть Array будет {1, 4, 45, 6, 10, -8} и сумма для поиска будет 16

Сортировать массив
A = {-8, 1, 4, 6, 10, 45}

Мы будем увеличивать 'l', когда сумма пары меньше требуемой суммы, и уменьшать 'r', когда сумма пары больше требуемой суммы.
Это потому, что когда сумма меньше требуемой, нам нужно получить число, которое может увеличить нашу сумму пары, чтобы мы двигались слева направо (также сортируется массив), таким образом, «l ++» и наоборот.

Инициализировать l = 0, r = 5
A [l] + A [r] (-8 + 45)> 16 => декремент r. Сейчас г = 4
Приращение A [l] + A [r] (-8 + 10) l. Теперь l = 1
A [l] + A [r] (1 + 10) приращение l. Теперь l = 2
A [l] + A [r] (4 + 10) приращение l. Теперь l = 3
A [l] + A [r] (6 + 10) == 16 => Найденные кандидаты (возврат 1)

Примечание. Если имеется более одной пары с заданной суммой, то этот алгоритм сообщает только об одной. Может быть легко расширен для этого, хотя.

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

C ++

// C ++ программа для проверки наличия данного массива
// имеет 2 элемента, сумма которых равна
// до заданного значения

  
#include <bits/stdc++.h>

using namespace std;

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

bool hasArrayTwoCandidates(int A[], int arr_size,

                           int sum)

{

    int l, r;

  

    / * Сортировка элементов * /

    sort(A, A + arr_size);

  

    / * Теперь ищем двух кандидатов в

       отсортированный массив * /

    l = 0;

    r = arr_size - 1;

    while (l < r) {

        if (A[l] + A[r] == sum)

            return 1;

        else if (A[l] + A[r] < sum)

            l++;

        else // A [i] + A [j]> сумма

            r--;

    }

    return 0;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int A[] = { 1, 4, 45, 6, 10, -8 };

    int n = 16;

    int arr_size = sizeof(A) / sizeof(A[0]);

  

    // вызов функции

    if (hasArrayTwoCandidates(A, arr_size, n))

        cout << "Array has two elements with given sum";

    else

        cout << "Array doesn't have two elements with given sum";

  

    return 0;

}

С

// C программа для проверки наличия данного массива
// имеет 2 элемента, сумма которых равна
// до заданного значения

  
#include <stdio.h>
#define bool int

  

void quickSort(int*, int, int);

  

bool hasArrayTwoCandidates(int A[], int arr_size, int sum)

{

    int l, r;

  

    / * Сортировка элементов * /

    quickSort(A, 0, arr_size - 1);

  

    / * Теперь ищем двух кандидатов в отсортированном

       массив * /

    l = 0;

    r = arr_size - 1;

    while (l < r) {

        if (A[l] + A[r] == sum)

            return 1;

        else if (A[l] + A[r] < sum)

            l++;

        else // A [i] + A [j]> сумма

            r--;

    }

    return 0;

}

  
/ * СЛЕДУЮЩИЕ ФУНКЦИИ ТОЛЬКО ДЛЯ СОРТИРОВКИ

    ЦЕЛЬ */

void exchange(int* a, int* b)

{

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

}

  

int partition(int A[], int si, int ei)

{

    int x = A[ei];

    int i = (si - 1);

    int j;

  

    for (j = si; j <= ei - 1; j++) {

        if (A[j] <= x) {

            i++;

            exchange(&A[i], &A[j]);

        }

    }

    exchange(&A[i + 1], &A[ei]);

    return (i + 1);

}

  
/ * Реализация быстрой сортировки
A [] -> Массив для сортировки
si -> Начальный индекс
ei -> Конечный индекс
* /

void quickSort(int A[], int si, int ei)

{

    int pi; / * Индекс разделения * /

    if (si < ei) {

        pi = partition(A, si, ei);

        quickSort(A, si, pi - 1);

        quickSort(A, pi + 1, ei);

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int A[] = { 1, 4, 45, 6, 10, -8 };

    int n = 16;

    int arr_size = 6;

  

    if (hasArrayTwoCandidates(A, arr_size, n))

        printf("Array has two elements with given sum");

    else

        printf("Array doesn't have two elements with given sum");

  

    getchar();

    return 0;

}

Джава

// Java программа для проверки наличия данного массива
// имеет 2 элемента, сумма которых равна
// до заданного значения

import java.util.*;

  

class GFG {

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

    // чья сумма равна заданному значению

    static boolean hasArrayTwoCandidates(int A[],

                                         int arr_size, int sum)

    {

        int l, r;

  

        / * Сортировка элементов * /

        Arrays.sort(A);

  

        / * Теперь ищем двух кандидатов

        в отсортированном массиве * /

        l = 0;

        r = arr_size - 1;

        while (l < r) {

            if (A[l] + A[r] == sum)

                return true;

            else if (A[l] + A[r] < sum)

                l++;

            else // A [i] + A [j]> сумма

                r--;

        }

        return false;

    }

  

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

    public static void main(String args[])

    {

        int A[] = { 1, 4, 45, 6, 10, -8 };

        int n = 16;

        int arr_size = A.length;

  

        // вызов функции

        if (hasArrayTwoCandidates(A, arr_size, n))

            System.out.println("Array has two "

                               + "elements with given sum");

        else

            System.out.println("Array doesn't have "

                               + "two elements with given sum");

    }

}

питон

# Программа Python для проверки выполнения условия суммы

  

def hasArrayTwoCandidates(A, arr_size, sum):

      

    # сортировать массив

    quickSort(A, 0, arr_size-1)

    l = 0

    r = arr_size-1

      

    # пройти массив для двух элементов

    while l<r:

        if (A[l] + A[r] == sum):

            return 1

        elif (A[l] + A[r] < sum):

            l += 1

        else:

            r -= 1

    return 0

  
# Реализация быстрой сортировки
# A [] -> Массив для сортировки
# si -> Начальный индекс
# ei -> Конечный индекс

def quickSort(A, si, ei):

    if si < ei:

        pi = partition(A, si, ei)

        quickSort(A, si, pi-1)

        quickSort(A, pi + 1, ei)

  
# Утилита для разбиения массива (используется в быстрой сортировке)

def partition(A, si, ei):

    x = A[ei]

    i = (si-1)

    for j in range(si, ei):

        if A[j] <= x:

            i += 1

              

            # Эта операция используется для замены двух переменных - это python

            A[i], A[j] = A[j], A[i]

  

        A[i + 1], A[ei] = A[ei], A[i + 1]

          

    return i + 1

      

  
# Драйвер программы для проверки функций

A = [1, 4, 45, 6, 10, -8]

n = 16

if (hasArrayTwoCandidates(A, len(A), n)):

    print("Array has two elements with the given sum")

else:

    print("Array doesn't have two elements with the given sum")

  
## Этот код предоставлен __Devesh Agrawal__

C #

// C # программа для проверки на пару
// в A [] с суммой как x

  

using System;

  

class GFG {

    static bool hasArrayTwoCandidates(int[] A,

                                      int arr_size, int sum)

    {

        int l, r;

  

        / * Сортировка элементов * /

        sort(A, 0, arr_size - 1);

  

        / * Теперь ищем двух кандидатов

        в отсортированном массиве * /

        l = 0;

        r = arr_size - 1;

        while (l < r) {

            if (A[l] + A[r] == sum)

                return true;

            else if (A[l] + A[r] < sum)

                l++;

            else // A [i] + A [j]> сумма

                r--;

        }

        return false;

    }

  

    / * Ниже приведены функции только для сортировки

    массив с использованием QuickSort * /

  

    / * Эта функция принимает последний элемент в качестве оси,

    помещает элемент поворота в правильное положение

    Положение в отсортированном массиве

    меньше (меньше, чем шарнир) слева от

    стержень и все большие элементы вправо

    оси * /

    static int partition(int[] arr, int low, int high)

    {

        int pivot = arr[high];

  

        // индекс меньшего элемента

        int i = (low - 1);

        for (int j = low; j <= high - 1; j++) {

            // Если текущий элемент меньше

            // чем или равно Pivot

            if (arr[j] <= pivot) {

                i++;

  

                // поменять местами arr [i] и arr [j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // поменять местами arr [i + 1] и arr [high] (или pivot)

        int temp1 = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp1;

  

        return i + 1;

    }

  

    / * Основная функция, которая

    реализует QuickSort ()

    arr [] -> Массив для сортировки,

    низкий -> Начальный индекс,

    высокий -> конечный индекс * /

    static void sort(int[] arr, int low, int high)

    {

        if (low < high) {

            / * pi - индекс разделения, arr [pi]

            сейчас в нужном месте * /

            int pi = partition(arr, low, high);

  

            // Рекурсивно сортировать элементы перед

            // раздел и после раздела

            sort(arr, low, pi - 1);

            sort(arr, pi + 1, high);

        }

    }

  

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

    public static void Main()

    {

        int[] A = { 1, 4, 45, 6, 10, -8 };

        int n = 16;

        int arr_size = 6;

  

        if (hasArrayTwoCandidates(A, arr_size, n))

            Console.Write("Array has two elements"

                          + " with given sum");

        else

            Console.Write("Array doesn't have "

                          + "two elements with given sum");

    }

}

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

PHP

<?php
// PHP программа для проверки, если дано
// массив имеет 2 элемента, чья сумма
// равно заданному значению

  
// Функция для проверки наличия массива
// 2 элемента, сумма которых равна
// до заданного значения

function hasArrayTwoCandidates($A, $arr_size,

                                        $sum)

{

    $l; $r;

  

    / * Сортировка элементов * /

    // sort ($ A, A + arr_size);

    sort($A);

  

    / * Теперь ищем двух кандидатов

    в отсортированном массиве * /

    $l = 0;

    $r = $arr_size - 1; 

    while ($l < $r)

    {

        if($A[$l] + $A[$r] == $sum)

            return 1; 

        else if($A[$l] + $A[$r] < $sum)

            $l++;

        else // A [i] + A [j]> сумма

            $r--;

    

    return 0;

}

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

$A = array (1, 4, 45, 6, 10, -8);

$n = 16;

$arr_size = sizeof($A);

  
// вызов функции

if(hasArrayTwoCandidates($A, $arr_size, $n))

    echo "Array has two elements " .

                   "with given sum";

else

    echo "Array doesn't have two "

          "elements with given sum";

      
// Этот код предоставлен m_kit
?>


Выход :

Array has two elements with the given sum

МЕТОД 2 (использовать хеширование)
Этот метод работает за O (n) раз.

1) Initialize an empty hash table s.
2) Do following for each element A[i] in A[]
   (a)    If s[x - A[i]] is set then print the pair (A[i], x - A[i])
   (b)    Insert A[i] into s.

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

C ++

// C ++ программа для проверки наличия данного массива
// имеет 2 элемента, сумма которых равна
// до заданного значения
#include <bits/stdc++.h>

  

using namespace std;

  

void printPairs(int arr[], int arr_size, int sum)

{

    unordered_set<int> s;

    for (int i = 0; i < arr_size; i++) {

        int temp = sum - arr[i];

  

        if (s.find(temp) != s.end())

            cout << "Pair with given sum " << sum << " is (" << arr[i] << ", " << temp << ")" << endl;

  

        s.insert(arr[i]);

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int A[] = { 1, 4, 45, 6, 10, 8 };

    int n = 16;

    int arr_size = sizeof(A) / sizeof(A[0]);

  

    // вызов функции

    printPairs(A, arr_size, n);

  

    return 0;

}

С

// C ++ программа для проверки наличия данного массива
// имеет 2 элемента, сумма которых равна
// до заданного значения

  
// Работает только если диапазон элементов ограничен
#include <stdio.h>
#define MAX 100000

  

void printPairs(int arr[], int arr_size, int sum)

{

    int i, temp;

    bool s[MAX] = { 0 }; / * инициализировать хэш, установленный в 0 * /

  

    for (i = 0; i < arr_size; i++) {

        temp = sum - arr[i];

        if (s[temp] == 1)

            printf("Pair with given sum %d is (%d, %d) n",

                   sum, arr[i], temp);

        s[arr[i]] = 1;

    }

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int A[] = { 1, 4, 45, 6, 10, 8 };

    int n = 16;

    int arr_size = sizeof(A) / sizeof(A[0]);

  

    printPairs(A, arr_size, n);

  

    getchar();

    return 0;

}

Джава

// Реализация Java с использованием хеширования

import java.io.*;

import java.util.HashSet;

  

class PairSum {

    static void printpairs(int arr[], int sum)

    {

        HashSet<Integer> s = new HashSet<Integer>();

        for (int i = 0; i < arr.length; ++i) {

            int temp = sum - arr[i];

  

            // проверка состояния

            if (s.contains(temp)) {

                System.out.println("Pair with given sum " + sum + " is (" + arr[i] + ", " + temp + ")");

            }

            s.add(arr[i]);

        }

    }

  

    // Main для проверки вышеуказанной функции

    public static void main(String[] args)

    {

        int A[] = { 1, 4, 45, 6, 10, 8 };

        int n = 16;

        printpairs(A, n);

    }

}

  
// Эта статья предоставлена Aakash Hasija

питон

# Программа Python, чтобы найти, если есть
# два элемента с заданной суммой

  
# функция для проверки заданной суммы
# в массиве

def printPairs(arr, arr_size, sum):

      

    # Создать пустой хэш

    s = set()

      

    for i in range(0, arr_size):

        temp = sum-arr[i]

        if (temp in s):

            print "Pair with given sum "+ str(sum) + " is (" + str(arr[i]) + ", " + str(temp) + ")"

        s.add(arr[i])

  
# драйверная программа для проверки вышеуказанной функции

A = [1, 4, 45, 6, 10, 8]

n = 16

printPairs(A, len(A), n)

  
# Этот код предоставлен __Devesh Agrawal__

C #

// реализация C # с использованием хеширования

using System;

using System.Collections.Generic;

  

class GFG {

    static void printpairs(int[] arr,

                           int sum)

    {

        HashSet<int> s = new HashSet<int>();

        for (int i = 0; i < arr.Length; ++i) {

            int temp = sum - arr[i];

  

            // проверка состояния

            if (s.Contains(temp)) {

                Console.Write("Pair with given sum " + sum + " is (" + arr[i] + ", " + temp + ")");

            }

            s.Add(arr[i]);

        }

    }

  

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

    static void Main()

    {

        int[] A = new int[] { 1, 4, 45,

                              6, 10, 8 };

        int n = 16;

        printpairs(A, n);

    }

}

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

Выход:

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

Учитывая массив A [] и число x, проверьте на пару в A [] с суммой как x

0.00 (0%) 0 votes