Posted on by Kalkicode
Code Array

# Find smallest pair sum in an array

The problem is to finding the smallest pair sum in an array. This problem is about identifying two elements from an array whose sum is the smallest among all possible pairs. This kind of problem often arises in optimization scenarios and is frequently encountered in programming interviews and competitive coding challenges.

## Problem Statement

Given an array of integers, we need to find the pair of elements whose sum is the smallest among all possible pairs in the array.

## Example

Let's consider an example to understand this problem:

Array: [10, 15, -7, 31, 33]

In this array, the pairs and their sums are:

• (10, 15): Sum = 25
• (10, -7): Sum = 3
• (10, 31): Sum = 41
• (10, 33): Sum = 43
• (15, -7): Sum = 8
• (15, 31): Sum = 46
• (15, 33): Sum = 48
• (-7, 31): Sum = 24
• (-7, 33): Sum = 26
• (31, 33): Sum = 64

The smallest pair sum is achieved by choosing (-7, 10) with a sum of 3.

## Idea to Solve

To solve this problem efficiently, we can use a greedy approach. Since we're looking for the smallest pair sum, we should consider the smallest elements in the array. We can achieve this by iterating through the array and comparing the sum of the current element with all other elements. We'll keep track of the smallest sum and the pair of elements that achieve this sum.

## Algorithm

1. Initialize variables `first` and `second` to store the indices of the pair with the smallest sum, and `minSum` to store the smallest sum (initialized to a large value).
2. Iterate through the array using two nested loops: one loop for the first element and another for the second element.
3. Calculate the sum of the current pair.
4. If the calculated sum is smaller than `minSum`, update `minSum`, `first`, and `second` accordingly.
5. After the loops, the pair with the smallest sum is `(arr[first], arr[second])`, and the smallest sum is `minSum`.

## Pseudocode

``````smallest_pair(arr, size):
if size < 2:
return

first = 0
second = 1
minSum = arr[0] + arr[1]

for i from 0 to size - 1:
for j from i + 1 to size:
currentSum = arr[i] + arr[j]
if currentSum < minSum:
minSum = currentSum
first = i
second = j

print("Array elements:", arr)
print("Smallest pair [", arr[first], ",", arr[second], "]:", minSum)``````

## Code Solution

``````// C Program
// Find smallest pair sum in an array
#include <stdio.h>

//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Find the pair of smallest sum in given array
void smallest_pair(int arr[], int size)
{
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
int sum = arr[0] + arr[1];
//Get the first pair indexes
int first = 0;
int second = 1;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] + arr[j] < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr[i] + arr[j];
//Get the location of new smallest pair
first = i;
second = j;
}
}
}
printf("\n Array elements : ");
display(arr, size);
//Display result
printf("\n Smallest pair [%d, %d] : %d\n", arr[first], arr[second], sum);
}
int main()
{
int a1[] = {
10 , 15 , -7 , 31 , 33
};
//Get the size of array
int size = sizeof(a1) / sizeof(a1[0]);
smallest_pair(a1, size);
int a2[] = {
9 , 6 , 1 , 5 , 8 , 3
};
//Get the size of array
size = sizeof(a2) / sizeof(a2[0]);
smallest_pair(a2, size);
return 0;
}``````

#### Output

`````` Array elements : 10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements : 9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````// Java Program
// Find median of two sorted arrays
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//Find the pair of smallest sum in given array
public void smallest_pair(int[] arr, int size)
{
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
int sum = arr[0] + arr[1];
//Get the first pair indexes
int first = 0;
int second = 1;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] + arr[j] < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr[i] + arr[j];
//Get the location of new smallest pair
first = i;
second = j;
}
}
}
System.out.print("\n Array elements : ");
display(arr, size);
System.out.print("\n Smallest pair [" + arr[first] + ", " + arr[second] + "] : " + sum + "\n");
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
int[] a1 = {
10,
15,
-7,
31,
33
};
//Get the size of array
int size = a1.length;
obj.smallest_pair(a1, size);
int[] a2 = {
9,
6,
1,
5,
8,
3
};
//Get the size of array
size = a2.length;
obj.smallest_pair(a2, size);
}
}``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find median of two sorted arrays
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Find the pair of smallest sum in given array
void smallest_pair(int arr[], int size)
{
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
int sum = arr[0] + arr[1];
//Get the first pair indexes
int first = 0;
int second = 1;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] + arr[j] < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr[i] + arr[j];
//Get the location of new smallest pair
first = i;
second = j;
}
}
}
cout << "\n Array elements : ";
this->display(arr, size);
cout << "\n Smallest pair [" << arr[first] << ", " << arr[second] << "] : " << sum << "\n";
}
};
int main()
{
MyArray obj = MyArray();
int a1[] = {
10 , 15 , -7 , 31 , 33
};
//Get the size of array
int size = sizeof(a1) / sizeof(a1[0]);
obj.smallest_pair(a1, size);
int a2[] = {
9 , 6 , 1 , 5 , 8 , 3
};
//Get the size of array
size = sizeof(a2) / sizeof(a2[0]);
obj.smallest_pair(a2, size);
return 0;
}``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````//Include namespace system
using System;

// C# Program
// Find median of two sorted arrays
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Find the pair of smallest sum in given array
public void smallest_pair(int[] arr, int size)
{
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
int sum = arr[0] + arr[1];
//Get the first pair indexes
int first = 0;
int second = 1;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] + arr[j] < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr[i] + arr[j];
//Get the location of new smallest pair
first = i;
second = j;
}
}
}
Console.Write("\n Array elements : ");
display(arr, size);
Console.Write("\n Smallest pair [" + arr[first] + ", " + arr[second] + "] : " + sum + "\n");
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] a1 = {
10 , 15 , -7 , 31 , 33
};
//Get the size of array
int size = a1.Length;
obj.smallest_pair(a1, size);
int[] a2 = {
9 , 6 , 1 , 5 , 8 , 3
};
//Get the size of array
size = a2.Length;
obj.smallest_pair(a2, size);
}
}``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````<?php
// Php Program
// Find median of two sorted arrays
class MyArray
{
//Function which is display array elements
public	function display( & \$arr, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo " ". \$arr[\$i];
}
echo "\n";
}
//Find the pair of smallest sum in given array
public	function smallest_pair( & \$arr, \$size)
{
if (\$size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
\$sum = \$arr[0] + \$arr[1];
//Get the first pair indexes
\$first = 0;
\$second = 1;
for (\$i = 0; \$i < \$size; ++\$i)
{
for (\$j = \$i + 1; \$j < \$size; ++\$j)
{
if (\$arr[\$i] + \$arr[\$j] < \$sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
\$sum = \$arr[\$i] + \$arr[\$j];
//Get the location of new smallest pair
\$first = \$i;
\$second = \$j;
}
}
}
echo "\n Array elements : ";
\$this->display(\$arr, \$size);
echo "\n Smallest pair [". \$arr[\$first] .", ". \$arr[\$second] ."] : ". \$sum ."\n";
}
}

function main()
{
\$obj = new MyArray();
\$a1 = array(10, 15, -7, 31, 33);
//Get the size of array
\$size = count(\$a1);
\$obj->smallest_pair(\$a1, \$size);
\$a2 = array(9, 6, 1, 5, 8, 3);
//Get the size of array
\$size = count(\$a2);
\$obj->smallest_pair(\$a2, \$size);
}
main();``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````// Node Js Program
// Find median of two sorted arrays
class MyArray
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Find the pair of smallest sum in given array
smallest_pair(arr, size)
{
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
var sum = arr[0] + arr[1];
//Get the first pair indexes
var first = 0;
var second = 1;
for (var i = 0; i < size; ++i)
{
for (var j = i + 1; j < size; ++j)
{
if (arr[i] + arr[j] < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr[i] + arr[j];
//Get the location of new smallest pair
first = i;
second = j;
}
}
}
process.stdout.write("\n Array elements : ");
this.display(arr, size);
process.stdout.write("\n Smallest pair [" + arr[first] + ", " + arr[second] + "] : " + sum + "\n");
}
}

function main()
{
var obj = new MyArray();
var a1 = [10, 15, -7, 31, 33];
//Get the size of array
var size = a1.length;
obj.smallest_pair(a1, size);
var a2 = [9, 6, 1, 5, 8, 3];
//Get the size of array
size = a2.length;
obj.smallest_pair(a2, size);
}
main();``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````#  Python 3 Program
#  Find median of two sorted arrays
class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

# Find the pair of smallest sum in given array
def smallest_pair(self, arr, size) :
if (size < 2) :
# When array contains less than 2 elements
return

# First pair sum
sum = arr[0] + arr[1]
# Get the first pair indexes
first = 0
second = 1
i = 0
while (i < size) :
j = i + 1
while (j < size) :
if (arr[i] + arr[j] < sum) :
# When get a new smallest  element pair
# Get the sum of new small pair
sum = arr[i] + arr[j]
# Get the location of new smallest pair
first = i
second = j

j += 1

i += 1

print("\n Array elements : ", end = "")
self.display(arr, size)
print("\n Smallest pair [", arr[first] ,", ", arr[second] ,"] : ", sum ,"\n", end = "")

def main() :
obj = MyArray()
a1 = [10, 15, -7, 31, 33]
# Get the size of array
size = len(a1)
obj.smallest_pair(a1, size)
a2 = [9, 6, 1, 5, 8, 3]
# Get the size of array
size = len(a2)
obj.smallest_pair(a2, size)

if __name__ == "__main__": main()``````

#### Output

`````` Array elements :   10  15  -7  31  33

Smallest pair [ 10 ,  -7 ] :  3

Array elements :   9  6  1  5  8  3

Smallest pair [ 1 ,  3 ] :  4``````
``````#  Ruby Program
#  Find median of two sorted arrays
class MyArray

# Function which is display array elements
def display(arr, size)

i = 0
while (i < size)

print(" ", arr[i])
i += 1
end
print("\n")
end
# Find the pair of smallest sum in given array
def smallest_pair(arr, size)

if (size < 2)

# When array contains less than 2 elements
return
end
# First pair sum
sum = arr[0] + arr[1]
# Get the first pair indexes
first = 0
second = 1
i = 0
while (i < size)

j = i + 1
while (j < size)

if (arr[i] + arr[j] < sum)

# When get a new smallest  element pair
# Get the sum of new small pair
sum = arr[i] + arr[j]
# Get the location of new smallest pair
first = i
second = j
end
j += 1
end
i += 1
end
print("\n Array elements : ")
self.display(arr, size)
print("\n Smallest pair [", arr[first] ,", ", arr[second] ,"] : ", sum ,"\n")
end
end
def main()

obj = MyArray.new()
a1 = [10, 15, -7, 31, 33]
# Get the size of array
size = a1.length
obj.smallest_pair(a1, size)
a2 = [9, 6, 1, 5, 8, 3]
# Get the size of array
size = a2.length
obj.smallest_pair(a2, size)
end
main()``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4
``````
``````// Scala Program
// Find median of two sorted arrays
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Find the pair of smallest sum in given array
def smallest_pair(arr: Array[Int], size: Int): Unit = {
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
var sum: Int = arr(0) + arr(1);
//Get the first pair indexes
var first: Int = 0;
var second: Int = 1;
var i: Int = 0;
while (i < size)
{
var j: Int = i + 1;
while (j < size)
{
if (arr(i) + arr(j) < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr(i) + arr(j);
//Get the location of new smallest pair
first = i;
second = j;
}
j += 1;
}
i += 1;
}
print("\n Array elements : ");
display(arr, size);
print("\n Smallest pair [" + arr(first) + ", " + arr(second) + "] : " + sum + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var a1: Array[Int] = Array(10, 15, -7, 31, 33);
//Get the size of array
var size: Int = a1.length;
obj.smallest_pair(a1, size);
var a2: Array[Int] = Array(9, 6, 1, 5, 8, 3);
//Get the size of array
size = a2.length;
obj.smallest_pair(a2, size);
}
}``````

#### Output

`````` Array elements :  10 15 -7 31 33

Smallest pair [10, -7] : 3

Array elements :  9 6 1 5 8 3

Smallest pair [1, 3] : 4``````
``````// Swift Program
// Find median of two sorted arrays
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Find the pair of smallest sum in given array
func smallest_pair(_ arr: [Int], _ size: Int)
{
if (size < 2)
{
//When array contains less than 2 elements
return;
}
//First pair sum
var sum: Int = arr[0] + arr[1];
//Get the first pair indexes
var first: Int = 0;
var second: Int = 1;
var i: Int = 0;
while (i < size)
{
var j: Int = i + 1;
while (j < size)
{
if (arr[i] + arr[j] < sum)
{
//When get a new smallest  element pair
//Get the sum of new small pair
sum = arr[i] + arr[j];
//Get the location of new smallest pair
first = i;
second = j;
}
j += 1;
}
i += 1;
}
print("\n Array elements : ", terminator: "");
self.display(arr, size);
print("\n Smallest pair [", arr[first] ,", ", arr[second] ,"] : ", sum ,"\n", terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
let a1: [Int] = [10, 15, -7, 31, 33];
//Get the size of array
var size: Int = a1.count;
obj.smallest_pair(a1, size);
let a2: [Int] = [9, 6, 1, 5, 8, 3];
//Get the size of array
size = a2.count;
obj.smallest_pair(a2, size);
}
main();``````

#### Output

`````` Array elements :   10  15  -7  31  33

Smallest pair [ 10 ,  -7 ] :  3

Array elements :   9  6  1  5  8  3

Smallest pair [ 1 ,  3 ] :  4``````

## Time Complexity

The time complexity of this algorithm is O(n^2), where n is the size of the array. This is because, in the worst case, we iterate through all possible pairs of elements in the array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post