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.

New Comment