Skip to main content

K maximum sum combinations from two arrays

Here given code implementation process.

//C Program
//K maximum sum combinations from two arrays
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
  int auxiliary=arr[first];
  arr[first]=arr[second];
  arr[second]=auxiliary;
}

int compare(int arr[],int left,int right,int root,int size)
{
  int location = -1;

  if(left < size &&  arr[left] > arr[root] )
  {

    if(right < size && arr[right] > arr[left])
    {
      swap(arr,right,root);
      location = right;
    }
    else
    {
      swap(arr,left,root);
      location = left;
    }
  }
  else if(right < size && arr[right] > arr[root])
  {
    swap(arr,right,root);
    location = right;
  }
  return location;
}
void heap(int arr[],int size,int root)
{
  int left  = 2*root+1;
  int right = 2*root+2;
 
  int next = compare(arr, left, right, root, size);
 
  if(next != -1)
  {
    heap(arr,size,next);
  }
}

void sort_element(int arr[],int size)
{
  
  for (int i = (size/2)-1; i >= 0; i--)
  {
    heap(arr,size,i);
  }
  for (int i = size-1; i >= 0; i--)
  {
    swap(arr, 0, i);
    heap(arr, i, 0);
  }
}


void max_sum_pairs(int first[],int second[],int s1,int s2,int k)
{
  
  if(k>s1 || k>s2)
  {
    //invalid pair
    return;
  }
  //Sort given array elements
  sort_element(first,s1);
  sort_element(second,s2);
  printf(" %d Maximum pairs",k );
  int i=1;
  while(i<=k)
  {
    printf("\n(%d %d) : %d",first[s1-i],second[s2-i],first[s1-i]+second[s2-i]);
    i++;
  }
  printf("\n");

}

int main()
{
  //Define collections of integer values
  int arr1[] = {6,8,2,-2,9,3,1};

  int arr2[] = {3,7,2,5,0,3,1,4,6};

  //Get size of arr1
  int s1 = sizeof(arr1)/sizeof(arr1[0]);
  //Get size of arr2
  int s2 = sizeof(arr2)/sizeof(arr2[0]);
 
  //Number of pairs
  int k = 4;
  
  max_sum_pairs(arr1,arr2,s1,s2,k);

  return 0;
}

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
/*
  C++ Program
  K maximum sum combinations from two arrays
*/
#include<iostream>

using namespace std;
class MyHeap {
	public:

    //Swap two element in array
    void swap(int arr[], int first, int second) {
      int auxiliary = arr[first];
      arr[first] = arr[second];
      arr[second] = auxiliary;
    }
	int compare(int arr[], int left, int right, int root, int size) {
		int location = -1;
		if (left < size && arr[left] > arr[root]) {
			if (right < size && arr[right] > arr[left]) {
				this->swap(arr, right, root);
				location = right;
			} else {
				this->swap(arr, left, root);
				location = left;
			}
		} else
		if (right < size && arr[right] > arr[root]) {
			this->swap(arr, right, root);
			location = right;
		}
		return location;
	}
	void heap(int arr[], int size, int root) {
		int left = 2 *root + 1;
		int right = 2 *root + 2;
		int next = this->compare(arr, left, right, root, size);
		if (next != -1) {
			this->heap(arr, size, next);
		}
	}
	void sort_element(int arr[], int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			this->heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			this->swap(arr, 0, i);
			this->heap(arr, i, 0);
		}
	}
	void max_sum_pairs(int first[], int second[], int s1, int s2, int k) {
		if (k > s1 || k > s2) {
			//invalid pair

			return;
		}
		//Sort given array elements
		this->sort_element(first, s1);
		this->sort_element(second, s2);
		cout << " " << k << " Maximum pairs";
		int i = 1;
		while (i <= k) {
			cout << "\n(" << first[s1 - i] << " " << second[s2 - i] << ") : " << (first[s1 - i] + second[s2 - i]);
			i++;
		}
		cout << "\n";
	}
};
int main() {
	MyHeap obj = MyHeap();
	int arr1[] = {
		6,
		8,
		2,
		-2,
		9,
		3,
		1
	};
	int arr2[] = {
		3,
		7,
		2,
		5,
		0,
		3,
		1,
		4,
		6
	};
	//Get the size of array
	int s1 = sizeof(arr1) / sizeof(arr1[0]);
	int s2 = sizeof(arr2) / sizeof(arr2[0]);
	//Number of pairs
	int k = 4;
	obj.max_sum_pairs(arr1, arr2, s1, s2, k);
	return 0;
}

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
/*
  Java Program
  K maximum sum combinations from two arrays
*/
public class MyHeap {
  
  //Swap two element in array
  public void swap(int []arr,int first,int second)
  {
    int auxiliary=arr[first];
    arr[first]=arr[second];
    arr[second]=auxiliary;
  }

  public int compare(int []arr,int left,int right,int root,int size)
  {
    int location = -1;

    if(left < size &&  arr[left] > arr[root] )
    {

      if(right < size && arr[right] > arr[left])
      {
        swap(arr,right,root);
        location = right;
      }
      else
      {
        swap(arr,left,root);
        location = left;
      }
    }
    else if(right < size && arr[right] > arr[root])
    {
      swap(arr,right,root);
      location = right;
    }
    return location;
  }
  public void heap(int []arr,int size,int root)
  {
    int left  = 2*root+1;
    int right = 2*root+2;
   
    int next = compare(arr, left, right, root, size);
   
    if(next != -1)
    {
      heap(arr,size,next);
    }
  }

  public void sort_element(int []arr,int size)
  {
    
    for (int i = (size/2)-1; i >= 0; i--)
    {
      heap(arr,size,i);
    }
    for (int i = size-1; i >= 0; i--)
    {
      swap(arr, 0, i);
      heap(arr, i, 0);
    }
  }


  public void max_sum_pairs(int []first,int []second,int s1,int s2,int k)
  {
    
    if(k>s1 || k>s2)
    {
      //invalid pair
      return;
    }
    //Sort given array elements
    sort_element(first,s1);
    sort_element(second,s2);
    System.out.print(" "+k+" Maximum pairs" );
    int i=1;
    while(i<=k)
    {
      System.out.print("\n("+first[s1-i]+" "+second[s2-i]+") : "+(first[s1-i]+second[s2-i]));
      i++;
    }
    System.out.print("\n");

  }
  
  public static void main(String[] args) {
    
    MyHeap obj = new MyHeap();
      
    //Define collections of integer values
    int []arr1 = {6,8,2,-2,9,3,1};

    int []arr2 = {3,7,2,5,0,3,1,4,6};    
    //Get the size of array
    int s1 = arr1.length;
    int s2 = arr2.length;
    //Number of pairs
    int k = 4;
    
    obj.max_sum_pairs(arr1,arr2,s1,s2,k);

  } 
}

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
/*
  C# Program
  K maximum sum combinations from two arrays
*/
using System;

public class MyHeap {
	//Swap two element in array
	public void swap(int[] arr, int first, int second) {
		int auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	public int compare(int[] arr, int left, int right, int root, int size) {
		int location = -1;
		if (left < size && arr[left] > arr[root]) {
			if (right < size && arr[right] > arr[left]) {
				swap(arr, right, root);
				location = right;
			} else {
				swap(arr, left, root);
				location = left;
			}
		} else
		if (right < size && arr[right] > arr[root]) {
			swap(arr, right, root);
			location = right;
		}
		return location;
	}
	public void heap(int[] arr, int size, int root) {
		int left = 2 * root + 1;
		int right = 2 * root + 2;
		int next = compare(arr, left, right, root, size);
		if (next != -1) {
			heap(arr, size, next);
		}
	}
	public void sort_element(int[] arr, int size) {
		for (int i = (size / 2) - 1; i >= 0; i--) {
			heap(arr, size, i);
		}
		for (int i = size - 1; i >= 0; i--) {
			swap(arr, 0, i);
			heap(arr, i, 0);
		}
	}
	public void max_sum_pairs(int[] first, int[] second, int s1, int s2, int k) {
		if (k > s1 || k > s2) {
			return;
		}
		sort_element(first, s1);
		sort_element(second, s2);
		Console.Write(" " + k + " Maximum pairs");
		int i = 1;
		while (i <= k) {
			Console.Write("\n(" + first[s1 - i] + " " + second[s2 - i] + ") : " + (first[s1 - i] + second[s2 - i]));
			i++;
		}
		Console.Write("\n");
	}
	public static void Main(String[] args) {
		MyHeap obj = new MyHeap();
      	//Define collections of integer values
		int[] arr1 = {
			6,
			8,
			2,
			-2,
			9,
			3,
			1
		};
		int[] arr2 = {
			3,
			7,
			2,
			5,
			0,
			3,
			1,
			4,
			6
		};
		//Get the size of array
		int s1 = arr1.Length;
		int s2 = arr2.Length;
		//Number of pairs
		int k = 4;
		obj.max_sum_pairs(arr1, arr2, s1, s2, k);
	}
}

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
<?php
/*
  Php Program
  K maximum sum combinations from two arrays
*/
class MyHeap {
	//Swap two element in array

	public 	function swap(&$arr, $first, $second) {
		$auxiliary = $arr[$first];
		$arr[$first] = $arr[$second];
		$arr[$second] = $auxiliary;
	}
	public 	function compare(&$arr, $left, $right, $root, $size) {
		$location = -1;
		if ($left < $size && $arr[$left] > $arr[$root]) {
			if ($right < $size && $arr[$right] > $arr[$left]) {
				$this->swap($arr, $right, $root);
				$location = $right;
			} else {
				$this->swap($arr, $left, $root);
				$location = $left;
			}
		} else
		if ($right < $size && $arr[$right] > $arr[$root]) {
			$this->swap($arr, $right, $root);
			$location = $right;
		}
		return $location;
	}
	public 	function heap(&$arr, $size, $root) {
		$left = 2 *$root + 1;
		$right = 2 *$root + 2;
		$next = $this->compare($arr, $left, $right, $root, $size);
		if ($next != -1) {
			$this->heap($arr, $size, $next);
		}
	}
	public 	function sort_element(&$arr, $size) {
		for ($i = (intval($size / 2)) - 1; $i >= 0; $i--) {
			$this->heap($arr, $size, $i);
		}
		for ($i = $size - 1; $i >= 0; $i--) {
			$this->swap($arr, 0, $i);
			$this->heap($arr, $i, 0);
		}
	}
	public 	function max_sum_pairs($first, $second, $s1, $s2, $k) {
		if ($k > $s1 || $k > $s2) {
			return;
		}
		//Sort given array elements
		$this->sort_element($first, $s1);
		$this->sort_element($second, $s2);
		echo(" ". $k ." Maximum pairs");
		$i = 1;
		while ($i <= $k) {
			echo("\n(". $first[$s1 - $i] ." ". $second[$s2 - $i] .") : ". ($first[$s1 - $i] + $second[$s2 - $i]));
			$i++;
		}
		echo("\n");
	}
}

function main() {
	$obj = new MyHeap();
	//Define collections of integer values
	$arr1 = array(6, 8, 2, -2, 9, 3, 1);
	$arr2 = array(3, 7, 2, 5, 0, 3, 1, 4, 6);
	//Get the size of array
	$s1 = count($arr1);
	$s2 = count($arr2);
	//Number of pairs
	$k = 4;
	$obj->max_sum_pairs($arr1, $arr2, $s1, $s2, $k);

}
main();

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
/*
  Node Js Program
  K maximum sum combinations from two arrays
*/
class MyHeap {
	//Swap two element in array
	swap(arr, first, second) {
		var auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	compare(arr, left, right, root, size) {
		var location = -1;
		if (left < size && arr[left] > arr[root]) {
			if (right < size && arr[right] > arr[left]) {
				this.swap(arr, right, root);
				location = right;
			} else {
				this.swap(arr, left, root);
				location = left;
			}
		} else
		if (right < size && arr[right] > arr[root]) {
			this.swap(arr, right, root);
			location = right;
		}

		return location;
	}
	heap(arr, size, root) {
		var left = 2 *root + 1;
		var right = 2 *root + 2;
		var next = this.compare(arr, left, right, root, size);
		if (next != -1) {
			this.heap(arr, size, next);
		}
	}
	sort_element(arr, size) {
		for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
			this.heap(arr, size, i);
		}

		for (var i = size - 1; i >= 0; i--) {
			this.swap(arr, 0, i);
			this.heap(arr, i, 0);
		}
	}
	max_sum_pairs(first, second, s1, s2, k) {
		if (k > s1 || k > s2) {
			return;
		}

		//Sort given array elements
		this.sort_element(first, s1);
		this.sort_element(second, s2);
		process.stdout.write(" " + k + " Maximum pairs");
		var i = 1;
		while (i <= k) {
			process.stdout.write("\n(" + first[s1 - i] + " " + second[s2 - i] + ") : " + (first[s1 - i] + second[s2 - i]));
			i++;
		}

		process.stdout.write("\n");
	}
}

function main(args) {
	var obj = new MyHeap();
	//Define collections of integer values
	var arr1 = [6, 8, 2, -2, 9, 3, 1];
	var arr2 = [3, 7, 2, 5, 0, 3, 1, 4, 6];
	//Get the size of array
	var s1 = arr1.length;
	var s2 = arr2.length;
	//Number of pairs
	var k = 4;
	obj.max_sum_pairs(arr1, arr2, s1, s2, k);
}

main();

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
#  Python 3 Program
#  K maximum sum combinations from two arrays

class MyHeap :
	# Swap two element in array
	def swap(self, arr, first, second) :
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	
	def compare(self, arr, left, right, root, size) :
		location = -1
		if (left < size and arr[left] > arr[root]) :
			if (right < size and arr[right] > arr[left]) :
				self.swap(arr, right, root)
				location = right
			else :
				self.swap(arr, left, root)
				location = left
			
		elif (right < size and arr[right] > arr[root]) :
			self.swap(arr, right, root)
			location = right
		
		return location
	
	def heap(self, arr, size, root) :
		left = 2 * root + 1
		right = 2 * root + 2
		next = self.compare(arr, left, right, root, size)
		if (next != -1) :
			self.heap(arr, size, next)
		
	
	def sort_element(self, arr, size) :
		i = (int(size / 2)) - 1
		while (i >= 0) :
			self.heap(arr, size, i)
			i -= 1
		
		i = size - 1
		while (i >= 0) :
			self.swap(arr, 0, i)
			self.heap(arr, i, 0)
			i -= 1
		
	
	def max_sum_pairs(self, first, second, s1, s2, k) :
		if (k > s1 or k > s2) :
			return
		
		self.sort_element(first, s1)
		self.sort_element(second, s2)
		print(" ", k ," Maximum pairs", end = "")
		i = 1
		while (i <= k) :
			print("\n(", first[s1 - i] ," ", second[s2 - i] ,") : ", (first[s1 - i] + second[s2 - i]), end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MyHeap()
	arr1 = [6, 8, 2, -2, 9, 3, 1]
	arr2 = [3, 7, 2, 5, 0, 3, 1, 4, 6]
	s1 = len(arr1)
	s2 = len(arr2)
	k = 4
	obj.max_sum_pairs(arr1, arr2, s1, s2, k)


if __name__ == "__main__":
	main()

Output

  4  Maximum pairs
( 9   7 ) :  16
( 8   6 ) :  14
( 6   5 ) :  11
( 3   4 ) :  7
#  Ruby Program
#  K maximum sum combinations from two arrays

class MyHeap 
	 # Swap two element in array
	def swap(arr, first, second) 
		auxiliary = arr[first]
		arr[first] = arr[second]
		arr[second] = auxiliary
	end
	def compare(arr, left, right, root, size) 
		location = -1
		if (left < size && arr[left] > arr[root]) 
			if (right < size && arr[right] > arr[left]) 
				self.swap(arr, right, root)
				location = right
			else 
				self.swap(arr, left, root)
				location = left
			end
		elsif (right < size && arr[right] > arr[root]) 
			self.swap(arr, right, root)
			location = right
		end
		return location
	end
	def heap(arr, size, root) 
		left = 2 * root + 1
		right = 2 * root + 2
		next_in = self.compare(arr, left, right, root, size)
		if (next_in != -1) 
			self.heap(arr, size, next_in)
		end
	end
	def sort_element(arr, size) 
		i = (size / 2) - 1
		while (i >= 0) 
			self.heap(arr, size, i)
			i -= 1
		end
		i = size - 1
		while (i >= 0) 
			self.swap(arr, 0, i)
			self.heap(arr, i, 0)
			i -= 1
		end
	end
	def max_sum_pairs(first, second, s1, s2, k) 
		if (k > s1 || k > s2) 
			return
		end
		self.sort_element(first, s1)
		self.sort_element(second, s2)
		print(" ", k ," Maximum pairs")
		i = 1
		while (i <= k) 
			print("\n(", first[s1 - i] ," ", second[s2 - i] ,")  :", (first[s1 - i] + second[s2 - i]))
			i += 1
		end
		print("\n")
	end
end
def main() 
	obj = MyHeap.new()
	arr1 = [6, 8, 2, -2, 9, 3, 1]
	arr2 = [3, 7, 2, 5, 0, 3, 1, 4, 6]
	s1 = arr1.length
	s2 = arr2.length
	k = 4
	obj.max_sum_pairs(arr1, arr2, s1, s2, k)
end
main()

Output

 4 Maximum pairs
(9 7)  :16
(8 6)  :14
(6 5)  :11
(3 4)  :7
/*
  Scala Program
  K maximum sum combinations from two arrays
*/
class MyHeap {
	//Swap two element in array
	def swap(arr: Array[Int], first: Int, second: Int): Unit = {
		val auxiliary: Int = arr(first);
		arr(first) = arr(second);
		arr(second) = auxiliary;
	}
	def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
		var location: Int = -1;

		if (left < size && arr(left) > arr(root)) {
			if (right < size && arr(right) > arr(left)) {
				this.swap(arr, right, root);
				location = right;
			} else {
				this.swap(arr, left, root);
				location = left;
			}
		} else
		if (right < size && arr(right) > arr(root)) {
			this.swap(arr, right, root);
			location = right;
		}
		return location;
	}
	def heap(arr: Array[Int], size: Int, root: Int): Unit = {
		val left: Int = 2 * root + 1;
		val right: Int = 2 * root + 2;
		val next: Int = this.compare(arr, left, right, root, size);

		if (next != -1) {
			this.heap(arr, size, next);
		}
	}
	def sort_element(arr: Array[Int], size: Int): Unit = {
		var i: Int = ((size / 2).toInt) - 1;
		while (i >= 0) {
			this.heap(arr, size, i);
			i -= 1;
		}
		i = size - 1;
		while (i >= 0) {
			this.swap(arr, 0, i);
			this.heap(arr, i, 0);
			i -= 1;
		}
	}
	def max_sum_pairs(first: Array[Int], second: Array[Int], s1: Int, s2: Int, k: Int): Unit = {
		if (k > s1 || k > s2) {
			return;
		}
		this.sort_element(first, s1);
		this.sort_element(second, s2);
		print(" " + k + " Maximum pairs");
		var i: Int = 1;
		while (i <= k) {
			print("\n(" + first(s1 - i) + " " + second(s2 - i) + ") : " + (first(s1 - i) + second(s2 - i)));
			i += 1;
		}
		print("\n");
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyHeap = new MyHeap();
		var arr1: Array[Int] = Array(6, 8, 2, -2, 9, 3, 1);
		var arr2: Array[Int] = Array(3, 7, 2, 5, 0, 3, 1, 4, 6);
		val s1: Int = arr1.length;
		val s2: Int = arr2.length;
		val k: Int = 4;
		obj.max_sum_pairs(arr1, arr2, s1, s2, k);
	}
}

Output

 4 Maximum pairs
(9 7) : 16
(8 6) : 14
(6 5) : 11
(3 4) : 7
/*
  Swift Program
  K maximum sum combinations from two arrays
*/
class MyHeap {
	//Swap two element in array
	func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
		let auxiliary = arr[first];
		arr[first] = arr[second];
		arr[second] = auxiliary;
	}
	func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
		var location = -1;
		if (left < size && arr[left] > arr[root]) {
			if (right < size && arr[right] > arr[left]) {
				self.swap(&arr, right, root);
				location = right;
			} else {
				self.swap(&arr, left, root);
				location = left;
			}
		} else
		if (right < size && arr[right] > arr[root]) {
			self.swap(&arr, right, root);
			location = right;
		}
		return location;
	}
	func heap(_ arr: inout [Int], _ size: Int, _ root: Int) {
		let left = 2 * root + 1;
		let right = 2 * root + 2;
		let next = self.compare(&arr, left, right, root, size);
		if (next != -1) {
			self.heap(&arr, size, next);
		}
	}
	func sort_element(_ arr: inout [Int], _ size: Int) {
		var i = (size / 2) - 1;
		while (i >= 0) {
			self.heap(&arr, size, i);
			i -= 1;
		}
		i = size - 1;
		while (i >= 0) {
			self.swap(&arr, 0, i);
			self.heap(&arr, i, 0);
			i -= 1;
		}
	}
	func max_sum_pairs(_ first: inout [Int], _ second: inout [Int], _ s1: Int, _ s2: Int, _ k: Int) {
		if (k > s1 || k > s2) {
			return;
		}
		self.sort_element(&first, s1);
		self.sort_element(&second, s2);
		print(" ", k ," Maximum pairs", terminator: "");
		var i = 1;
		while (i <= k) {
			print("\n(", first[s1 - i] ," ", second[s2 - i] ,") : ", (first[s1 - i] + second[s2 - i]), terminator: "");
			i += 1;
		}
		print("\n", terminator: "");
	}
}
func main() {
	let obj = MyHeap();
	var arr1 = [6, 8, 2, -2, 9, 3, 1];
	var arr2 = [3, 7, 2, 5, 0, 3, 1, 4, 6];
	let s1 = arr1.count;
	let s2 = arr2.count;
	let k = 4;
	obj.max_sum_pairs(&arr1, &arr2, s1, s2, k);
}
main();

Output

  4  Maximum pairs
( 9   7 ) :  16
( 8   6 ) :  14
( 6   5 ) :  11
( 3   4 ) :  7




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