Рубрики

Два элемента, сумма которых ближе всего к нулю

Вопрос: Дан массив целых чисел, + ve и -ve. Вам нужно найти два элемента так, чтобы их сумма была ближе всего к нулю.

Для приведенного ниже массива программа должна вывести -80 и 85.

МЕТОД 1 (простой)
Для каждого элемента найдите его сумму с каждым другим элементом в массиве и сравните суммы. Наконец, верните минимальную сумму.

Реализация :

C ++

# include <bits/stdc++.h>
# include <stdlib.h> /* for abs() */
# include <math.h>

  

using namespace std;

void minAbsSumPair(int arr[], int arr_size)

{

    int inv_count = 0;

    int l, r, min_sum, sum, min_l, min_r;

      

    / * Массив должен иметь как минимум

       два элемента * /

    if(arr_size < 2)

    {

        cout << "Invalid Input";

        return;

    }

      

    / * Инициализация значений * /

    min_l = 0;

    min_r = 1;

    min_sum = arr[0] + arr[1];

      

    for(l = 0; l < arr_size - 1; l++)

    {

        for(r = l + 1; r < arr_size; r++)

        {

        sum = arr[l] + arr[r];

        if(abs(min_sum) > abs(sum))

        {

            min_sum = sum;

            min_l = l;

            min_r = r;

        }

        }

    }

      

    cout << "The two elements whose sum is minimum are "

         << arr[min_l] << " and " << arr[min_r];

}

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

int main()

{

    int arr[] = {1, 60, -10, 70, -80, 85};

    minAbsSumPair(arr, 6);

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай (Abby_akku)

С

# include <stdio.h>
# include <stdlib.h> /* for abs() */
# include <math.h>

void minAbsSumPair(int arr[], int arr_size)

{

  int inv_count = 0;

  int l, r, min_sum, sum, min_l, min_r;

  

  / * Массив должен иметь как минимум два элемента * /

  if(arr_size < 2)

  {

    printf("Invalid Input");

    return;

  }

  

  / * Инициализация значений * /

  min_l = 0;

  min_r = 1;

  min_sum = arr[0] + arr[1];

  

  for(l = 0; l < arr_size - 1; l++)

  {

    for(r = l+1; r < arr_size; r++)

    {

      sum = arr[l] + arr[r];

      if(abs(min_sum) > abs(sum))

      {

        min_sum = sum;

        min_l = l;

        min_r = r;

      }

    }

  }

  

  printf(" The two elements whose sum is minimum are %d and %d",

          arr[min_l], arr[min_r]);

}

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

int main()

{

  int arr[] = {1, 60, -10, 70, -80, 85};

  minAbsSumPair(arr, 6);

  getchar();

  return 0;

}

Джава

import java.util.*;

import java.lang.*;

class Main

{

    static void minAbsSumPair(int arr[], int arr_size)

    {

      int inv_count = 0;

      int l, r, min_sum, sum, min_l, min_r;

       

      / * Массив должен иметь как минимум два элемента * /

      if(arr_size < 2)

      {

        System.out.println("Invalid Input");

        return;

      }

       

      / * Инициализация значений * /

      min_l = 0;

      min_r = 1;

      min_sum = arr[0] + arr[1];

       

      for(l = 0; l < arr_size - 1; l++)

      {

        for(r = l+1; r < arr_size; r++)

        {

          sum = arr[l] + arr[r];

          if(Math.abs(min_sum) > Math.abs(sum))

          {

            min_sum = sum;

            min_l = l;

            min_r = r;

          }

        }

      }

       

      System.out.println(" The two elements whose "+

                              "sum is minimum are "+

                        arr[min_l]+ " and "+arr[min_r]);

    }

      

    // основная функция

    public static void main (String[] args) 

    {

        int arr[] = {1, 60, -10, 70, -80, 85};

        minAbsSumPair(arr, 6);

    }

      
}

python3

# Python3 код для поиска двух элементов
# чья сумма ближе всего к нулю

  

def minAbsSumPair(arr,arr_size):

    inv_count = 0

  

    # Массив должен иметь как минимум

    # два элемента

    if arr_size < 2:

        print("Invalid Input")

        return

  

    # Инициализация значений

    min_l = 0

    min_r = 1

    min_sum = arr[0] + arr[1]

    for l in range (0, arr_size - 1):

        for r in range (l + 1, arr_size):

            sum = arr[l] + arr[r]                 

            if abs(min_sum) > abs(sum):         

                min_sum = sum

                min_l = l

                min_r = r

  

    print("The two elements whose sum is minimum are"

            arr[min_l], "and ", arr[min_r])

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

arr = [1, 60, -10, 70, -80, 85]

  

minAbsSumPair(arr, 6);

  
# Этот код предоставлен Смитой Динеш Семвал

C #

// C # код для поиска двух элементов
// чья сумма ближе всего к нулю

using System;

  

class GFG

{

static void minAbsSumPair(int []arr,

                        int arr_size)

    {

      

    int l, r, min_sum, sum, min_l, min_r;

      

    / * Массив должен иметь как минимум два элемента * /

    if (arr_size < 2)

    {

        Console.Write("Invalid Input");

        return;

    }

      

    / * Инициализация значений * /

    min_l = 0;

    min_r = 1;

    min_sum = arr[0] + arr[1];

      

    for (l = 0; l < arr_size - 1; l++)

    {

        for (r = l+1; r < arr_size; r++)

        {

            sum = arr[l] + arr[r];

            if (Math.Abs(min_sum) > Math.Abs(sum))

            {

                min_sum = sum;

                min_l = l;

                min_r = r;

            }

        }

    }

      

    Console.Write(" The two elements whose "+

                        "sum is minimum are "+

                    arr[min_l]+ " and "+arr[min_r]);

    }

      

    // основная функция

    public static void Main () 

    {

        int []arr = {1, 60, -10, 70, -80, 85};

      

        minAbsSumPair(arr, 6);

    }

      
}

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

PHP

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

  

function minAbsSumPair($arr, $arr_size)

{

    $inv_count = 0;

      

    / * Массив должен иметь в

    минимум два элемента * /

    if($arr_size < 2)

    {

        echo "Invalid Input";

        return;

    }

      

    / * Инициализация значений * /

    $min_l = 0;

    $min_r = 1;

    $min_sum = $arr[0] + $arr[1];

      

    for($l = 0; $l < $arr_size - 1; $l++)

    {

        for($r = $l+1; $r < $arr_size; $r++)

        {

        $sum = $arr[$l] + $arr[$r];

        if(abs($min_sum) > abs($sum))

        {

            $min_sum = $sum;

            $min_l = $l;

            $min_r = $r;

        }

        }

    }

      

    echo "The two elements whose sum is minimum are "

            .$arr[$min_l]." and ". $arr[$min_r];

              
}

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

$arr = array(1, 60, -10, 70, -80, 85);

minAbsSumPair($arr, 6);

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

Выход:

The two elements whose sum is minimum are -80 and 85

Сложность времени: O (n ^ 2)

МЕТОД 2 (использовать сортировку)
Спасибо Баскину за предложение такого подхода. Мы рекомендуем прочитать этот пост для фона этого подхода.

Алгоритм
1) Сортировка всех элементов входного массива.
2) Используйте две индексные переменные l и r для перемещения с левого и правого концов соответственно. Инициализируйте l как 0 и r как n-1.
3) сумма = a [l] + a [r]
4) Если сумма равна -ve, то l ++
5) Если сумма + ve, то r–
6) Следите за минимальной суммой.
7) Повторите шаги 3, 4, 5 и 6, пока l <r

Реализация

C ++

#include <bits/stdc++.h>

using namespace std;

  

void quickSort(int *, int, int); 

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

   с минимальной суммой * /

void minAbsSumPair(int arr[], int n) 

          

    // Переменные для отслеживания

    // текущей суммы и минимальной суммы

    int sum, min_sum = INT_MAX; 

      

    // левые и правые индексные переменные

    int l = 0, r = n-1; 

      

    // переменная для отслеживания

    // левая и правая пара для min_sum

    int min_l = l, min_r = n-1; 

      

    / * Массив должен иметь как минимум два элемента * /

    if(n < 2) 

    

        cout << "Invalid Input"

        return

    

      

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

    quickSort(arr, l, r); 

      

    while(l < r) 

    

        sum = arr[l] + arr[r]; 

      

        / * Если abs (сумма) меньше

          затем обновите элементы результата * /

        if(abs(sum) < abs(min_sum)) 

        

            min_sum = sum; 

            min_l = l; 

            min_r = r; 

        

        if(sum < 0) 

            l++; 

        else

            r--; 

    

      

    cout << "The two elements whose sum is minimum are " 

         << arr[min_l] << " and " << arr[min_r]; 

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

int main() 

    int arr[] = {1, 60, -10, 70, -80, 85}; 

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

    minAbsSumPair(arr, n); 

    return 0; 

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

   ЦЕЛЬ СОРТИРОВКИ * /

void exchange(int *a, int *b) 

    int temp; 

    temp = *a; 

    *a = *b; 

    *b = temp; 

  

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

    int x = arr[ei]; 

    int i = (si - 1); 

    int j; 

      

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

    

        if(arr[j] <= x) 

        

            i++; 

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

        

    

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

    return (i + 1); 

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

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

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

    if(si < ei) 

    

        pi = partition(arr, si, ei); 

        quickSort(arr, si, pi - 1); 

        quickSort(arr, pi + 1, ei); 

    

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

С

# include <stdio.h>
# include <math.h>
# include <limits.h>

  

void quickSort(int *, int, int);

  
/ * Функция для вывода пары элементов с минимальной суммой * /

void minAbsSumPair(int arr[], int n)

{

  // Переменные для отслеживания текущей суммы и минимальной суммы

  int sum, min_sum = INT_MAX;

  

  // левые и правые индексные переменные

  int l = 0, r = n-1;

  

  // переменная для отслеживания левой и правой пары для min_sum

  int min_l = l, min_r = n-1;

  

  / * Массив должен иметь как минимум два элемента * /

  if(n < 2)

  {

    printf("Invalid Input");

    return;

  }

  

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

  quickSort(arr, l, r);

  

  while(l < r)

  {

    sum = arr[l] + arr[r];

  

    / * Если abs (сумма) меньше, обновите элементы результата * /

    if(abs(sum) < abs(min_sum))

    {

      min_sum = sum;

      min_l = l;

      min_r = r;

    }

    if(sum < 0)

      l++;

    else

      r--;

  }

  

  printf(" The two elements whose sum is minimum are %d and %d",

          arr[min_l], arr[min_r]);

}

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

int main()

{

  int arr[] = {1, 60, -10, 70, -80, 85};

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

  minAbsSumPair(arr, n);

  getchar();

  return 0;

}

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

    ЦЕЛЬ */

void exchange(int *a, int *b)

{

  int temp;

  temp = *a;

  *a   = *b;

  *b   = temp;

}

  

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

{

  int x = arr[ei];

  int i = (si - 1);

  int j;

  

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

  {

    if(arr[j] <= x)

    {

      i++;

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

    }

  }

  

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

  return (i + 1);

}

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

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

{

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

  if(si < ei)

  {

    pi = partition(arr, si, ei);

    quickSort(arr, si, pi - 1);

    quickSort(arr, pi + 1, ei);

  }

}

Джава

import java.util.*;

import java.lang.*;

class Main

{

    static void minAbsSumPair(int arr[], int n)

    {

      // Переменные для отслеживания текущей суммы и минимальной суммы

      int sum, min_sum = 999999;

       

      // левые и правые индексные переменные

      int l = 0, r = n-1;

       

      // переменная для отслеживания левой и правой пары для min_sum

      int min_l = l, min_r = n-1;

       

      / * Массив должен иметь как минимум два элемента * /

      if(n < 2)

      {

        System.out.println("Invalid Input");

        return;

      }

       

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

      sort(arr, l, r);

       

      while(l < r)

      {

        sum = arr[l] + arr[r];

       

        / * Если abs (сумма) меньше, обновите элементы результата * /

        if(Math.abs(sum) < Math.abs(min_sum))

        {

          min_sum = sum;

          min_l = l;

          min_r = r;

        }

        if(sum < 0)

          l++;

        else

          r--;

      }

       

        

      System.out.println(" The two elements whose "+

                              "sum is minimum are "+

                        arr[min_l]+ " and "+arr[min_r]);

    }

       

    // основная функция

    public static void main (String[] args) 

    {

        int arr[] = {1, 60, -10, 70, -80, 85};

        int n = arr.length;

        minAbsSumPair(arr, n);

    }

      

    / * Функции для быстрой сортировки * /

      

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

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

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

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

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

       оси * /

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

    {

        int pivot = arr[high]; 

        int i = (low-1); // индекс меньшего элемента

        for (int j=low; j<high; 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 temp = arr[i+1];

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

        arr[high] = temp;

  

        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);

        }

    }

}

python3

# Функция для привязки элементов
# с минимальной суммой * /

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

def partition(arr, si, ei):

    x = arr[ei]

    i = (si - 1)

  

    for j in range(si,ei):

        if(arr[j] <= x):

            i += 1

            arr[i], arr[j] = arr[j], arr[i]

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

    return (i + 1

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

def quickSort(arr, si, ei):

    pi = 0 # Индекс разбиения * /

    if(si < ei):

        pi = partition(arr, si, ei)

        quickSort(arr, si, pi - 1)

        quickSort(arr, pi + 1, ei)

  

def minAbsSumPair(arr, n):

  

    # Переменные для отслеживания

    # текущей суммы и минимальной суммы

    sum, min_sum = 0, 10**9

  

    # левая и правая индексные переменные

    l = 0

    r = n - 1

  

    # переменная для отслеживания

    # левая и правая пара для min_sum

    min_l = l

    min_r = n - 1

  

    # Массив должен иметь как минимум два элемента * /

    if(n < 2):

        print("Invalid Input", end = "")

        return

  

    # Сортировать элементы * /

    quickSort(arr, l, r)

  

    while(l < r):

        sum = arr[l] + arr[r]

  

        # Если абс (сумма) меньше

        # затем обновить элементы результата

        if(abs(sum) < abs(min_sum)):

            min_sum = sum

            min_l = l

            min_r = r

        if(sum < 0):

            l += 1

        else:

            r -= 1

  

    print("The two elements whose sum is minimum are"

                        arr[min_l], "and", arr[min_r])

  
Код водителя

arr = [1, 60, -10, 70, -80, 85

n = len(arr)

minAbsSumPair(arr, n)

  
# Этот код предоставлен mohit kumar 29

C #

using System;

  

class GFG

{

    static void minAbsSumPair(int []arr ,int n)

    {

        // Переменные для отслеживания

        // текущей суммы и минимальной суммы

        int sum, min_sum = 999999;

          

        // левые и правые индексные переменные

        int l = 0, r = n-1;

          

        // переменная для отслеживания левого

        // и правильная пара для min_sum

        int min_l = l, min_r = n-1;

          

        / * Массив должен иметь как минимум два элемента * /

        if (n < 2)

        {

            Console.Write("Invalid Input");

            return;

        }

          

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

        sort(arr, l, r);

          

        while(l < r)

        {

            sum = arr[l] + arr[r];

          

            / * Если abs (сумма) меньше, обновите элементы результата * /

            if (Math.Abs(sum) < Math.Abs(min_sum))

            {

                min_sum = sum;

                min_l = l;

                min_r = r;

            }

            if (sum < 0)

                l++;

            else

                r--;

        }

          

        Console.Write(" The two elements whose "

                                "sum is minimum are " +

                            arr[min_l]+ " and " + arr[min_r]);

    }

      

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

    public static void Main () 

    {

        int []arr = {1, 60, -10, 70, -80, 85};

        int n = arr.Length;

          

        minAbsSumPair(arr, n);

    }

      

    / * Функции для быстрой сортировки * /

      

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

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

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

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

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

    оси * /

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

    {

        int pivot = arr[high]; 

        int i = (low-1); // индекс меньшего элемента

          

        for (int j = low; j < high; 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);

        }

    }

}

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


Выход:

The two elements whose sum is minimum are -80 and 85


Сложность времени:
сложность сортировки + сложность поиска оптимальной пары = O (nlogn) + O (n) = O (nlogn)

STL реализация метода-2 :

Алгоритм
1) Сортировка всех элементов входного массива по абсолютным значениям.
2) Проверьте абсолютную сумму arr [i-1] и arr [i], если их абсолютная сумма меньше, чем min update min с их абсолютным значением.
3) Используйте две переменные для хранения индекса элементов.

Реализация

C ++

// реализация C ++ с использованием STL
#include <bits/stdc++.h>

using namespace std;

  
// Модифицировано для сортировки по абсолютным значениям

bool compare(int x, int y)

{

    return abs(x) < abs(y);

}

  

void findMinSum(int arr[], int n)

{

    sort(arr, arr + n, compare);

    int min = INT_MAX, x, y;

    for (int i = 1; i < n; i++) {

  

        // Абсолютное значение показывает, насколько оно близко к нулю

        if (abs(arr[i - 1] + arr[i]) <= min) {

  

            // если найдено даже близкое значение

            // обновляем min и сохраняем индекс

            min = abs(arr[i - 1] + arr[i]);

            x = i - 1;

            y = i;

        }

    }

    cout << "The two elements whose sum is minimum are "

         << arr[x] << " and " << arr[y];

}

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

int main()

{

  

    int arr[] = { 1, 60, -10, 70, -80, 85 };

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

    findMinSum(arr, n);

    return 0;

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

}


Выход:

The two elements whose sum is minimum are -80 and 85


Сложность времени: O (nlogn)
Космическая сложность: O (1)

Спросил Vineet.

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанной программе / алгоритме или другие способы решения той же проблемы.

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

Два элемента, сумма которых ближе всего к нулю

0.00 (0%) 0 votes