Given an array arr[] containing N distinct integers, the task is to find a contiguous pair such that the sum of both elements in the pair is minimum.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: (1, 2)
Explanation:
Here, contiguous pairs with their sum are (1, 2) = 3, (2, 3) = 5, (3, 4) = 7 and the minimum is 3.
Input: arr[] = {4, 9, -3, 2, 0}
Output: (-3, 2)
Explanation:
Here, contiguous pairs with their sum are (4, 9) = 13, (9, -3) = 6, (-3, 2) = -1, (2, 0) = 2
Approach:
To solve the problem mentioned above, we have to consider all the contiguous pairs and find their sum. The pair having the smallest(minimum) sum is the required answer.
Below is the implementation of the above approach:
C++
//C++ program to find the smallest// sum contiguous pair#include<bits/stdc++.h>using namespace std; // Function to find the smallest sum// contiguous pairvector<int> smallestSumpair(int arr[], int n){ // Contiguous pair vector<int>pair; // Initialize minimum sum // with maximum value int min_sum = INT_MAX; for(int i = 1; i < n; i++) { // Checking for minimum value if( min_sum > (arr[i] + arr[i - 1])) { min_sum = arr[i] + arr[i - 1]; if (pair.empty()) { // Add to pair pair.push_back(arr[i - 1]); pair.push_back(arr[i]); } else { // Updating pair pair[0] = arr[i - 1]; pair[1] = arr[i]; } } } return pair;} // Driver codeint main(){ int arr[] = {4, 9, -3, 2, 0}; int n = sizeof(arr) / sizeof(arr[0]); vector<int>pair = smallestSumpair(arr, n); cout << pair[0] << " " << pair[1];}// This code is contributed by chitranayal |
Java
// Java program to find the smallest// sum contiguous pair import java.util.*;class GFG{ // Function to find the smallest sum// contiguous pairpublic static Vector<Integer> smallestSumpair(int[] arr, int n) { // Stores the contiguous pair Vector<Integer> pair = new Vector<Integer>(); // Initialize minimum sum int min_sum = Integer.MAX_VALUE, i; for(i = 1; i < n; i++) { // Checking for minimum value if (min_sum > (arr[i] + arr[i - 1])) { min_sum = arr[i] + arr[i - 1]; if (pair.isEmpty()) { // Add to pair pair.add(arr[i - 1]); pair.add(arr[i]); } else { // Updating pair pair.set(0, arr[i - 1]); pair.set(1, arr[i]); } } } return pair;} // Driver Code public static void main(String[] args){ int arr[] = { 4, 9, -3, 2, 0 }; int N = arr.length; Vector<Integer> pair = new Vector<Integer>(); pair = smallestSumpair(arr, N); System.out.println(pair.get(0) + " " + pair.get(1));}}// This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to find the smallest# sum contiguous pair# importing sysimport sys# Function to find the smallest sum# contiguous pairdef smallestSumpair(arr, n): # Contiguous pair pair = [] # Initialize minimum sum # with maximum value min_sum = sys.maxsize for i in range(1, n): # checking for minimum value if min_sum > (arr[i] + arr[i-1]): min_sum = arr[i] + arr[i-1] if pair == []: # Add to pair pair.append(arr[i-1]) pair.append(arr[i]) else: # Updating pair pair[0] = arr[i-1] pair[1] = arr[i] return pair# Driver codearr = [4, 9, -3, 2, 0]n = len(arr)pair = smallestSumpair(arr, n)print(pair[0], pair[1]) |
C#
// C# program to find the smallest// sum contiguous pair using System;using System.Collections; using System.Collections.Generic;class GFG{// Function to find the smallest sum// contiguous pairpublic static ArrayList smallestSumpair(int[] arr, int n) { // Stores the contiguous pair ArrayList pair = new ArrayList(); // Initialize minimum sum int min_sum = int.MaxValue, i; for(i = 1; i < n; i++) { // Checking for minimum value if (min_sum > (arr[i] + arr[i - 1])) { min_sum = arr[i] + arr[i - 1]; if (pair.Count == 0) { // Add to pair pair.Add(arr[i - 1]); pair.Add(arr[i]); } else { // Updating pair pair[0] = arr[i - 1]; pair[1] = arr[i]; } } } return pair;} // Driver codepublic static void Main(string[] args){ int []arr = { 4, 9, -3, 2, 0 }; int N = arr.Length; ArrayList pair = new ArrayList(); pair = smallestSumpair(arr, N); Console.Write(pair[0] + " " + pair[1]);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript program to find the smallest// sum contiguous pair // Function to find the smallest sum// contiguous pairfunction smallestSumpair(arr,n){ // Stores the contiguous pair let pair = []; // Initialize minimum sum let min_sum = Number.MAX_VALUE, i; for(i = 1; i < n; i++) { // Checking for minimum value if (min_sum > (arr[i] + arr[i - 1])) { min_sum = arr[i] + arr[i - 1]; if (pair.length==0) { // Add to pair pair.push(arr[i - 1]); pair.push(arr[i]); } else { // Updating pair pair[0] = arr[i - 1]; pair[1] = arr[i]; } } } return pair;}// Driver Code let arr=[4, 9, -3, 2, 0 ];let N = arr.length; let pair = smallestSumpair(arr, N);document.write(pair[0] + " " + pair[1]); // This code is contributed by rag2127</script> |
Output
-3 2
Time Complexity: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
