Skip to main content

K minimum sum combinations from two arrays

Here given code implementation process.

//C Program
//K minimum 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 min_sum_pairs(int first[],int second[],int s1,int s2,int k)
{
  
  if(k>s1 || k>s2 || k<=0)
  {
    //invalid pair
    return;
  }
  sort_element(first,s1);
  sort_element(second,s2);
  printf(" %d Minimum pairs",k );
  int i=0;
  while(i<k)
  {
    printf("\n(%d %d) : %d",first[i],second[i],first[i]+second[i]);
    i++;
  }
  printf("\n");

}

 int main()
 {

  int arr1[] = {6,8,2,9,3,1};

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

  // Get the size of given arrays
  int s1 = sizeof(arr1)/sizeof(arr1[0]);

  int s2 = sizeof(arr2)/sizeof(arr2[0]);
 
  int k = 4;
  
  min_sum_pairs(arr1,arr2,s1,s2,k);
  return 0;
}

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
/*
  C++ Program
  K minimum 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 min_sum_pairs(int first[], int second[], int s1, int s2, int k) {
		if (k > s1 || k > s2 || k <= 0) {
			//invalid pair

			return;
		}
		this->sort_element(first, s1);
		this->sort_element(second, s2);
		cout << " " << k << " Minimum pairs";
		int i = 0;
		while (i < k) {
			cout << "\n(" << first[i] << " " << second[i] << ") : " << (first[i] + second[i]);
			i++;
		}
		cout << "\n";
	}
};
int main() {
	MyHeap obj = MyHeap();
	int arr1[] = {
		6,
		8,
		2,
		9,
		3,
		1
	};
	int arr2[] = {
		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.min_sum_pairs(arr1, arr2, s1, s2, k);
	return 0;
}

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
/*
  Java Program
  K minimum 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 min_sum_pairs(int []first,int []second,int s1,int s2,int k)
  {
    
    if(k>s1 || k>s2 || k<=0)
    {
      //invalid pair
      return;
    }
    sort_element(first,s1);
    sort_element(second,s2);
    System.out.print(" "+k+" Minimum pairs" );
    int i=0;
    while(i<k)
    {
      System.out.print("\n("+first[i]+" "+second[i]+") : "+(first[i]+second[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,9,3,1};

    int []arr2 = {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.min_sum_pairs(arr1,arr2,s1,s2,k);

  } 
}

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
/*
  C# Program
  K minimum 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 min_sum_pairs(int[] first, int[] second, int s1, int s2, int k) {
		if (k > s1 || k > s2 || k <= 0) {
			return;
		}
		sort_element(first, s1);
		sort_element(second, s2);
		Console.Write(" " + k + " Minimum pairs");
		int i = 0;
		while (i < k) {
			Console.Write("\n(" + first[i] + " " + second[i] + ") : " + (first[i] + second[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,
			9,
			3,
			1
		};
		int[] arr2 = {
			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.min_sum_pairs(arr1, arr2, s1, s2, k);
	}
}

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
<?php
/*
  Php Program
  K minimum 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 min_sum_pairs($first, $second, $s1, $s2, $k) {
		if ($k > $s1 || $k > $s2 || $k <= 0) {
			return;
		}
		$this->sort_element($first, $s1);
		$this->sort_element($second, $s2);
		echo(" ". $k ." Minimum pairs");
		$i = 0;
		while ($i < $k) {
			echo("\n(". $first[$i] ." ". $second[$i] .") : ". ($first[$i] + $second[$i]));
			$i++;
		}
		echo("\n");
	}
}

function main() {
	$obj = new MyHeap();
	//Define collections of integer values
	$arr1 = array(6, 8, 2, 9, 3, 1);
	$arr2 = array(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->min_sum_pairs($arr1, $arr2, $s1, $s2, $k);

}
main();

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
/*
  Node Js Program
  K minimum 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);
		}
	}
	min_sum_pairs(first, second, s1, s2, k) {
		if (k > s1 || k > s2 || k <= 0) {
			return;
		}
		this.sort_element(first, s1);
		this.sort_element(second, s2);
		process.stdout.write(" " + k + " Minimum pairs");
		var i = 0;
		while (i < k) {
			process.stdout.write("\n(" + first[i] + " " + second[i] + ") : " + (first[i] + second[i]));
			i++;
		}

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

function main(args) {
	var obj = new MyHeap();
	//Define collections of integer values
	var arr1 = [6, 8, 2, 9, 3, 1];
	var arr2 = [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.min_sum_pairs(arr1, arr2, s1, s2, k);
}

main();

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
#  Python 3 Program
#  K minimum 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 min_sum_pairs(self, first, second, s1, s2, k) :
		if (k > s1 or k > s2 or k <= 0) :
			return
		
		self.sort_element(first, s1)
		self.sort_element(second, s2)
		print(" ", k ," Minimum pairs", end = "")
		i = 0
		while (i < k) :
			print("\n(", first[i] ," ", second[i] ,") : ", (first[i] + second[i]), end = "")
			i += 1
		
		print("\n", end = "")
	

def main() :
	obj = MyHeap() # Define collections of integer values
	arr1 = [6, 8, 2, 9, 3, 1]
	arr2 = [7, 2, 5, 0, 3, 1, 4, 6] # Get the size of array
	s1 = len(arr1)
	s2 = len(arr2) # Number of pairs
	k = 4
	obj.min_sum_pairs(arr1, arr2, s1, s2, k)


if __name__ == "__main__":
	main()

Output

  4  Minimum pairs
( 1   0 ) :  1
( 2   1 ) :  3
( 3   2 ) :  5
( 6   3 ) :  9
#  Ruby Program
#  K minimum 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 min_sum_pairs(first, second, s1, s2, k) 
		if (k > s1 || k > s2 || k <= 0) 
			return
		end
		self.sort_element(first, s1)
		self.sort_element(second, s2)
		print(" ", k ," Minimum pairs")
		i = 0
		while (i < k) 
			print("\n(", first[i] ," ", second[i] ,")  :", (first[i] + second[i]))
			i += 1
		end
		print("\n")
	end
end
def main() 
	obj = MyHeap.new()
	 # Define collections of integer values
	arr1 = [6, 8, 2, 9, 3, 1]
	arr2 = [7, 2, 5, 0, 3, 1, 4, 6]
	 # Get the size of array
	s1 = arr1.length
	s2 = arr2.length
	 # Number of pairs
	k = 4
	obj.min_sum_pairs(arr1, arr2, s1, s2, k)
end
main()

Output

 4 Minimum pairs
(1 0)  :1
(2 1)  :3
(3 2)  :5
(6 3)  :9
/*
  Scala Program
  K minimum 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 min_sum_pairs(first: Array[Int], second: Array[Int], s1: Int, s2: Int, k: Int): Unit = {
		if (k > s1 || k > s2 || k <= 0) {
			return;
		}
		this.sort_element(first, s1);
		this.sort_element(second, s2);
		print(" " + k + " Minimum pairs");
		var i: Int = 0;
		while (i < k) {
			print("\n(" + first(i) + " " + second(i) + ") : " + (first(i) + second(i)));
			i += 1;
		}
		print("\n");
	}
}
object Main {
	def main(args: Array[String]): Unit = {
		val obj: MyHeap = new MyHeap();

		//Define collections of integer values
		var arr1: Array[Int] = Array(6, 8, 2, 9, 3, 1);
		var arr2: Array[Int] = Array(7, 2, 5, 0, 3, 1, 4, 6);

		//Get the size of array
		val s1: Int = arr1.length;
		val s2: Int = arr2.length;

		//Number of pairs
		val k: Int = 4;
		obj.min_sum_pairs(arr1, arr2, s1, s2, k);
	}
}

Output

 4 Minimum pairs
(1 0) : 1
(2 1) : 3
(3 2) : 5
(6 3) : 9
/*
  Swift Program
  K minimum 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 min_sum_pairs(_  first: inout [Int], _ second: inout [Int], _ s1: Int, _ s2: Int, _ k: Int) {
		if (k > s1 || k > s2 || k <= 0) {
			return;
		}
		self.sort_element(&first, s1);
		self.sort_element(&second, s2);
		print(" ", k ," Minimum pairs", terminator: "");
		var i = 0;
		while (i < k) {
			print("\n(", first[i] ," ", second[i] ,") : ", (first[i] + second[i]), terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
}
func main() {
	let obj = MyHeap();
	//Define collections of integer values
	var arr1 = [6, 8, 2, 9, 3, 1];
	var arr2 = [7, 2, 5, 0, 3, 1, 4, 6];
	//Get the size of array
	let s1 = arr1.count;
	let s2 = arr2.count;
	//Number of pairs
	let k = 4;
	obj.min_sum_pairs(&arr1, &arr2, s1, s2, k);
}
main();

Output

  4  Minimum pairs
( 1   0 ) :  1
( 2   1 ) :  3
( 3   2 ) :  5
( 6   3 ) :  9




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