Find the largest pair sum in an unsorted array
The problem you're tackling involves finding the largest sum that can be obtained by adding two numbers from an unsorted array. Specifically, you need to find the two largest elements in the array and calculate their sum.
Problem Statement
Given an unsorted array of integers, the task is to find the largest possible sum of any two numbers from the array.
Example
Consider the array arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
.
The largest pair sum is obtained by adding the largest elements, which are 9 and 8. Thus, the largest sum is 17.
Idea to Solve
To find the largest pair sum, you need to identify the two largest elements in the array. One approach is to iterate through the array and maintain indices for the two largest elements encountered so far. By the end of the iteration, you will have identified the two largest elements, and their sum will be the largest pair sum.
Algorithm
- Create a function
largest_sum(arr[], size)
:- Initialize variables
first
andsecond
to hold indices of the two largest elements. - Iterate through the array:
- If the current element is greater than the element at index
first
, updatefirst
with the current index. - If the current element is greater than the element at index
second
, updatesecond
with the current index.
- If the current element is greater than the element at index
- Display the largest pair sum, which is the sum of
arr[first]
andarr[second]
.
- Initialize variables
Pseudocode
function largest_sum(arr[], size):
if size <= 1:
return
first = 0
second = size - 1
for i from 0 to size - 1:
if arr[i] > arr[first]:
first = i
if arr[i] > arr[second]:
second = i
display "(", arr[first], ",", arr[second], ") :", arr[first] + arr[second]
main():
arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
size = size of arr
largest_sum(arr, size)
Program
//C Program
//Find the largest pair sum in an unsorted array
#include <stdio.h>
//Find the sum of largest pair in an unsorted array
void largest_sum(int arr[],int size)
{
if(size<=1)
{
return;
}
//Set initial array index
int first = 0;
int second =size-1;
for (int i = 0,j=size-1; i < size; ++i,j--)
{
if(i!=second && arr[i] > arr[first])
{
//When get a new max element
first = i;
}
if(j!=first && arr[j]>arr[second])
{
second=j;
}
}
//Display the sum of two largest element
printf("(%d ,%d) : %d\n",arr[first],arr[second] ,arr[first]+arr[second]);
}
int main()
{
//Define the value of array elements
int arr[] = {6,2,9,5,-2,4,8,2,7,1,3};
//Get the size of array
int size=sizeof(arr)/sizeof(arr[0]);
largest_sum(arr,size);
return 0;
}
Output
(9 ,8) : 17
#include<iostream>
using namespace std;
/*
C++ Program
Find the largest pair sum in an unsorted array
*/
class MyArray {
public:
//Find the sum of largest pair in an unsorted array
void largest_sum(int arr[], int size) {
if (size <= 1) {
return;
}
//Set initial array index
int first = 0;
int second = size - 1;
for (int i = 0, j = size - 1; i < size; ++i, j--) {
if (i != second && arr[i] > arr[first]) {
//When get a new max element
first = i;
}
if (j != first && arr[j] > arr[second]) {
second = j;
}
}
//Display the sum of two largest element
cout << "(" << arr[first] << " ," << arr[second] << ") : " << (arr[first] + arr[second]) << "\n";
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
6,
2,
9,
5,
-2,
4,
8,
2,
7,
1,
3
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.largest_sum(arr, size);
return 0;
}
Output
(9 ,8) : 17
/*
Java Program
Find the largest pair sum in an unsorted array
*/
public class MyArray
{
//Find the sum of largest pair in an unsorted array
public void largest_sum(int []arr,int size)
{
if(size<=1)
{
return;
}
//Set initial array index
int first = 0;
int second =size-1;
for (int i = 0,j=size-1; i < size; ++i,j--)
{
if(i!=second && arr[i] > arr[first])
{
//When get a new max element
first = i;
}
if(j!=first && arr[j]>arr[second])
{
second=j;
}
}
//Display the sum of two largest element
System.out.print("("+arr[first]+" ,"+arr[second]+") : "+(arr[first]+arr[second])+"\n");
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define the value of array elements
int []arr = {6,2,9,5,-2,4,8,2,7,1,3};
//Get the size of array
int size = arr.length;
obj.largest_sum(arr,size);
}
}
Output
(9 ,8) : 17
/*
C# Program
Find the largest pair sum in an unsorted array
*/
using System;
public class MyArray {
//Find the sum of largest pair in an unsorted array
public void largest_sum(int[] arr, int size) {
if (size <= 1) {
return;
}
//Set initial array index
int first = 0;
int second = size - 1;
for (int i = 0, j = size - 1; i < size; ++i, j--) {
if (i != second && arr[i] > arr[first]) {
//When get a new max element
first = i;
}
if (j != first && arr[j] > arr[second]) {
second = j;
}
}
Console.Write("(" + arr[first] + " ," + arr[second] + ") : " + (arr[first] + arr[second]) + "\n");
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[]
//Define the value of array elements
arr = {
6,
2,
9,
5,
-2,
4,
8,
2,
7,
1,
3
};
//Get the size of array
int size = arr.Length;
obj.largest_sum(arr, size);
}
}
Output
(9 ,8) : 17
<?php
/*
Php Program
Find the largest pair sum in an unsorted array
*/
class MyArray {
//Find the sum of largest pair in an unsorted array
public function largest_sum($arr, $size) {
if ($size <= 1) {
return;
}
//Set initial array index
$first = 0;
$second = $size - 1;
for ($i = 0, $j = $size - 1; $i < $size; ++$i, $j--) {
if ($i != $second && $arr[$i] > $arr[$first]) {
//When get a new max element
$first = $i;
}
if ($j != $first && $arr[$j] > $arr[$second]) {
$second = $j;
}
}
//Display the sum of two largest element
echo("(". $arr[$first] ." ,". $arr[$second] .") : ". ($arr[$first] + $arr[$second]) ."\n");
}
}
function main() {
$obj = new MyArray();
//Define the value of array elements
$arr = array(6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3);
//Get the size of array
$size = count($arr);
$obj->largest_sum($arr, $size);
}
main();
Output
(9 ,8) : 17
/*
Node Js Program
Find the largest pair sum in an unsorted array
*/
class MyArray {
//Find the sum of largest pair in an unsorted array
largest_sum(arr, size) {
if (size <= 1) {
return;
}
//Set initial array index
var first = 0;
var second = size - 1;
for (var i = 0,j = size - 1; i < size; ++i, j--) {
if (i != second && arr[i] > arr[first]) {
//When get a new max element
first = i;
}
if (j != first && arr[j] > arr[second]) {
second = j;
}
}
//Display the sum of two largest element
process.stdout.write("(" + arr[first] + " ," + arr[second] + ") : " + (arr[first] + arr[second]) + "\n");
}
}
function main(args) {
var obj = new MyArray();
//Define the value of array elements
var arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3];
//Get the size of array
var size = arr.length;
obj.largest_sum(arr, size);
}
main();
Output
(9 ,8) : 17
# Python 3 Program
# Find the largest pair sum in an unsorted array
class MyArray :
# Find the sum of largest pair in an unsorted array
def largest_sum(self, arr, size) :
if (size <= 1) :
return
first = 0
second = size - 1
i = 0
j = size - 1
while (i < size) :
if (i != second and arr[i] > arr[first]) :
# When get a new max element
first = i
if (j != first and arr[j] > arr[second]) :
second = j
i += 1
j -= 1
print("(", arr[first] ," ,", arr[second] ,") : ", (arr[first] + arr[second]) ,"\n", end = "")
def main() :
obj = MyArray()
arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
size = len(arr)
obj.largest_sum(arr, size)
if __name__ == "__main__":
main()
Output
( 9 , 8 ) : 17
# Ruby Program
# Find the largest pair sum in an unsorted array
class MyArray
# Find the sum of largest pair in an unsorted array
def largest_sum(arr, size)
if (size <= 1)
return
end
first = 0
second = size - 1
i = 0
j = size - 1
while (i < size)
if (i != second && arr[i] > arr[first])
# When get a new max element
first = i
end
if (j != first && arr[j] > arr[second])
second = j
end
i += 1
j -= 1
end
print("(", arr[first] ," ,", arr[second] ,") :", (arr[first] + arr[second]) ,"\n")
end
end
def main()
obj = MyArray.new()
arr = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3]
size = arr.length
obj.largest_sum(arr, size)
end
main()
Output
(9 ,8) :17
/*
Scala Program
Find the largest pair sum in an unsorted array
*/
class MyArray {
//Find the sum of largest pair in an unsorted array
def largest_sum(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
}
var first: Int = 0;
var second: Int = size - 1;
var i: Int = 0;
var j: Int = size - 1;
while (i < size) {
if (i != second && arr(i) > arr(first)) {
//When get a new max element
first = i;
}
if (j != first && arr(j) > arr(second)) {
second = j;
}
i += 1;
j -= 1;
}
print("(" + arr(first) + " ," + arr(second) + ") : " + (arr(first) + arr(second)) + "\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3);
val size: Int = arr.length;
obj.largest_sum(arr, size);
}
}
Output
(9 ,8) : 17
/*
Swift Program
Find the largest pair sum in an unsorted array
*/
class MyArray {
//Find the sum of largest pair in an unsorted array
func largest_sum(_ arr: [Int], _ size: Int) {
if (size <= 1) {
return;
}
var first: Int = 0;
var second: Int = size - 1;
var i: Int = 0;
var j: Int = size - 1;
while (i < size) {
if (i != second && arr[i] > arr[first]) {
//When get a new max element
first = i;
}
if (j != first && arr[j] > arr[second]) {
second = j;
}
i += 1;
j -= 1;
}
print("(", arr[first] ,",", arr[second] ,") :", (arr[first] + arr[second]) ,"\n", terminator: "");
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [6, 2, 9, 5, -2, 4, 8, 2, 7, 1, 3];
let size: Int = arr.count;
obj.largest_sum(arr, size);
}
main();
Output
( 9 , 8 ) : 17
Time Complexity
The algorithm iterates through the array once, and each iteration takes constant time operations (comparisons and assignments). Therefore, the time complexity of the solution is O(n), where 'n' is the size of the array.
Result Explanation
The algorithm identifies the two largest elements in the array and calculates their sum, which represents the largest
pair sum. In the example array, the largest elements are 9 and 8, and their sum is 17. The output line shows the
largest pair along with its sum: (9, 8) : 17
. This demonstrates how the algorithm effectively finds the
largest pair sum in an unsorted array.
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