Skip to main content

Count all distinct pairs with sum equal to k

Here given code implementation process.

import java.util.HashMap;
// Java program for
// Count all distinct pairs with sum equal to k
public class DistinctPairs
{
	// Display array elements
	public void printArray(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public void distinctPairOfKsum(int[] arr, int n, int k)
	{
		int count = 0;
		// Use to collect frequency of array elements
		HashMap < Integer, Integer > record = 
          		new HashMap < Integer, Integer > ();
		for (int i = 0; i < n; ++i)
		{
			if (record.containsKey(arr[i]))
			{
				// When key exists then increase the counter frequency
				record.put(arr[i], record.get(arr[i]) + 1);
			}
			else
			{
				record.put(arr[i], 1);
			}
		}
		for (int key: record.keySet())
		{
			if (key *2 == k && record.get(key) > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.containsKey(k - key))
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = count / 2;
		}
		// Display given array
		printArray(arr, n);
		// Display calculated result
		System.out.println("\n Resultant distinct pair of sum (" + 
                           k + ") is :  " + count);
	}
	public static void main(String[] args)
	{
		DistinctPairs task = new DistinctPairs();
		int[] arr1 = {
			2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0
		};
		int[] arr2 = {
			4 , -2 , 2 , 3 , 4 , 7
		};
		int n = arr1.length;
		// Test A
		int k = 4;
		/*
		    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]

		    sum k = 4   

		    (2,2) (4, 0) (1, 3)
		    -------------------

		   Resultant pair : 3
		*/
		task.distinctPairOfKsum(arr1, n, k);
		// Test B
		// Get length of arr2 
		n = arr2.length;
		k = 5;
		/*
		    arr = [  4 , -2 , 2 , 3 , 4 , 7]

		    sum k = 5   

		    (-2 + 7) (2 + 3) 
		    -------------------

		    Resultant pair : 2
		*/
		task.distinctPairOfKsum(arr2, n, k);
		// Test C
		k = 3;
		/*
		    arr = [  4 , -2 , 2 , 3 , 4 , 7]

		    sum k = 3   

		    None (no pair of sum 3)
		    -------------------

		    Resultant pair : 0
		*/
		task.distinctPairOfKsum(arr2, n, k);
	}
}

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
// Include header file
#include <iostream>

#include <unordered_map>

using namespace std;
// C++ program for
// Count all distinct pairs with sum equal to k
class DistinctPairs
{
	public:
		// Display array elements
		void printArray(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
		}
	void distinctPairOfKsum(int arr[], int n, int k)
	{
		int count = 0;
		// Use to collect frequency of array elements
		unordered_map < int, int > record;
		for (int i = 0; i < n; ++i)
		{
			if (record.find(arr[i]) != record.end())
			{
				// When key exists then increase the counter frequency
				record[arr[i]] = record[arr[i]] + 1;
			}
			else
			{
				record[arr[i]] = 1;
			}
		}
		for (auto &info: record)
		{
			if (info.first *2 == k && record[info.first] > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.find(k - info.first) != record.end())
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = count / 2;
		}
		// Display given array
		this->printArray(arr, n);
		// Display calculated result
		cout << "\n Resultant distinct pair of sum (" 
      		 << k << ") is :  " << count << endl;
	}
};
int main()
{
	DistinctPairs *task = new DistinctPairs();
	int arr1[] = {
		2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0
	};
	int arr2[] = {
		4 , -2 , 2 , 3 , 4 , 7
	};
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// Test A
	int k = 4;
	/*
	    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	    sum k = 4   
	    (2,2) (4, 0) (1, 3)
	    -------------------
	    Resultant pair : 3
	        
	*/
	task->distinctPairOfKsum(arr1, n, k);
	// Test B
	// Get length of arr2
	n = sizeof(arr2) / sizeof(arr2[0]);
	k = 5;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 5   
	    (-2 + 7) (2 + 3) 
	    -------------------
	    Resultant pair : 2
	        
	*/
	task->distinctPairOfKsum(arr2, n, k);
	// Test C
	k = 3;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 3   
	    None (no pair of sum 3)
	    -------------------
	    Resultant pair : 0
	        
	*/
	task->distinctPairOfKsum(arr2, n, k);
	return 0;
}

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Count all distinct pairs with sum equal to k
public class DistinctPairs
{
	// Display array elements
	public void printArray(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public void distinctPairOfKsum(int[] arr, int n, int k)
	{
		int count = 0;
		// Use to collect frequency of array elements
		Dictionary < int, int > record = new Dictionary < int, int > ();
		for (int i = 0; i < n; ++i)
		{
			if (record.ContainsKey(arr[i]))
			{
				// When key exists then increase the counter frequency
				record[arr[i]] = record[arr[i]] + 1;
			}
			else
			{
				record.Add(arr[i], 1);
			}
		}
		foreach(KeyValuePair < int, int > info in record)
		{
			if (info.Key * 2 == k && info.Value > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.ContainsKey(k - info.Key))
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = count / 2;
		}
		// Display given array
		this.printArray(arr, n);
		// Display calculated result
		Console.WriteLine("\n Resultant distinct pair of sum (" + k + ") is :  " + count);
	}
	public static void Main(String[] args)
	{
		DistinctPairs task = new DistinctPairs();
		int[] arr1 = {
			2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0
		};
		int[] arr2 = {
			4 , -2 , 2 , 3 , 4 , 7
		};
		int n = arr1.Length;
		// Test A
		int k = 4;
		/*
		    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
		    sum k = 4   
		    (2,2) (4, 0) (1, 3)
		    -------------------
		    Resultant pair : 3
		        
		*/
		task.distinctPairOfKsum(arr1, n, k);
		// Test B
		// Get length of arr2
		n = arr2.Length;
		k = 5;
		/*
		    arr = [  4 , -2 , 2 , 3 , 4 , 7]
		    sum k = 5   
		    (-2 + 7) (2 + 3) 
		    -------------------
		    Resultant pair : 2
		        
		*/
		task.distinctPairOfKsum(arr2, n, k);
		// Test C
		k = 3;
		/*
		    arr = [  4 , -2 , 2 , 3 , 4 , 7]
		    sum k = 3   
		    None (no pair of sum 3)
		    -------------------
		    Resultant pair : 0
		        
		*/
		task.distinctPairOfKsum(arr2, n, k);
	}
}

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
package main
import "fmt"
// Go program for
// Count all distinct pairs with sum equal to k

// Display array elements
func printArray(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
func distinctPairOfKsum(arr[] int, n int, k int) {
	var count int = 0
	// Use to collect frequency of array elements
	var record = make(map[int] int)
	for i := 0 ; i < n ; i++ {
		if _, found := record[arr[i]] ; found {
			// When key exists then increase the counter frequency
			record[arr[i]] = record[arr[i]] + 1
		} else {
			record[arr[i]] = 1
		}
	}
	for key, value := range record {
		if key * 2 == k && value > 1 {
			// When element is half of given k
			// And element appears more than once.
			count += 2
		} else if _, found := record[k - key] ; found {
			// When pair of sum k exists
			count += 1
		}
	}
	if count > 0 {
		count = count / 2
	}
	// Display given array
	printArray(arr, n)
	// Display calculated result
	fmt.Println("\n Resultant distinct pair of sum (", k, ") is :  ", count)
}
func main() {

	var arr1 = [] int { 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0}
	var arr2 = [] int { 4 , -2 , 2 , 3 , 4 , 7}
	var n int = len(arr1)
	// Test A
	var k int = 4
	/*
	    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	    sum k = 4   
	    (2,2) (4, 0) (1, 3)
	    -------------------
	    Resultant pair : 3
	        
	*/
	distinctPairOfKsum(arr1, n, k)
	// Test B
	// Get length of arr2
	n = len(arr2)
	k = 5
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 5   
	    (-2 + 7) (2 + 3) 
	    -------------------
	    Resultant pair : 2
	        
	*/
	distinctPairOfKsum(arr2, n, k)
	// Test C
	k = 3
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 3   
	    None (no pair of sum 3)
	    -------------------
	    Resultant pair : 0
	        
	*/
	distinctPairOfKsum(arr2, n, k)
}

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
<?php
// Php program for
// Count all distinct pairs with sum equal to k
class DistinctPairs
{
	// Display array elements
	public	function printArray($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	public	function distinctPairOfKsum($arr, $n, $k)
	{
		$count = 0;
		// Use to collect frequency of array elements
		$record = array();
		for ($i = 0; $i < $n; ++$i)
		{
			if (array_key_exists($arr[$i], $record))
			{
				// When key exists then increase the counter frequency
				$record[$arr[$i]] = $record[$arr[$i]] + 1;
			}
			else
			{
				$record[$arr[$i]] = 1;
			}
		}
		foreach($record as $key => $value)
		{
			if ($key * 2 == $k && $value > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				$count += 2;
			}
			else if (array_key_exists($k - $key, $record))
			{
				// When pair of sum k exists
				$count += 1;
			}
		}
		if ($count > 0)
		{
			$count = (int)($count / 2);
		}
		// Display given array
		$this->printArray($arr, $n);
		// Display calculated result
		echo("\n Resultant distinct pair of sum (".$k.
			") is :  ".$count.
			"\n");
	}
}

function main()
{
	$task = new DistinctPairs();
	$arr1 = array(2, 1, 4, 3, 5, 2, 1, 2, 0);
	$arr2 = array(4, -2, 2, 3, 4, 7);
	$n = count($arr1);
	// Test A
	$k = 4;
	/*
	    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	    sum k = 4   
	    (2,2) (4, 0) (1, 3)
	    -------------------
	    Resultant pair : 3
	        
	*/
	$task->distinctPairOfKsum($arr1, $n, $k);
	// Test B
	// Get length of arr2
	$n = count($arr2);
	$k = 5;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 5   
	    (-2 + 7) (2 + 3) 
	    -------------------
	    Resultant pair : 2
	        
	*/
	$task->distinctPairOfKsum($arr2, $n, $k);
	// Test C
	$k = 3;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 3   
	    None (no pair of sum 3)
	    -------------------
	    Resultant pair : 0
	        
	*/
	$task->distinctPairOfKsum($arr2, $n, $k);
}
main();

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
// Node JS program for
// Count all distinct pairs with sum equal to k
class DistinctPairs
{
	// Display array elements
	printArray(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	distinctPairOfKsum(arr, n, k)
	{
		var count = 0;
		// Use to collect frequency of array elements
		var record = new Map();
		for (var i = 0; i < n; ++i)
		{
			if (record.has(arr[i]))
			{
				// When key exists then increase the counter frequency
				record.set(arr[i], record.get(arr[i]) + 1);
			}
			else
			{
				record.set(arr[i], 1);
			}
		}
		for (let [key, value] of record)
		{
			if (key * 2 == k && value > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.has(k - key))
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = parseInt(count / 2);
		}
		// Display given array
		this.printArray(arr, n);
		// Display calculated result
		console.log("\n Resultant distinct pair of sum (" + 
                    k + ") is :  " + count);
	}
}

function main()
{
	var task = new DistinctPairs();
	var arr1 = [2, 1, 4, 3, 5, 2, 1, 2, 0];
	var arr2 = [4, -2, 2, 3, 4, 7];
	var n = arr1.length;
	// Test A
	var k = 4;
	/*
	    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	    sum k = 4   
	    (2,2) (4, 0) (1, 3)
	    -------------------
	    Resultant pair : 3
	        
	*/
	task.distinctPairOfKsum(arr1, n, k);
	// Test B
	// Get length of arr2
	n = arr2.length;
	k = 5;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 5   
	    (-2 + 7) (2 + 3) 
	    -------------------
	    Resultant pair : 2
	        
	*/
	task.distinctPairOfKsum(arr2, n, k);
	// Test C
	k = 3;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 3   
	    None (no pair of sum 3)
	    -------------------
	    Resultant pair : 0
	        
	*/
	task.distinctPairOfKsum(arr2, n, k);
}
main();

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
#  Python 3 program for
#  Count all distinct pairs with sum equal to k
class DistinctPairs :
	#  Display list elements
	def printArray(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	def distinctPairOfKsum(self, arr, n, k) :
		count = 0
		#  Use to collect frequency of list elements
		record = dict()
		i = 0
		while (i < n) :
			if ((arr[i] in record.keys())) :
				#  When key exists then increase the counter frequency
				record[arr[i]] = record.get(arr[i]) + 1
			else :
				record[arr[i]] = 1
			
			i += 1
		
		for key, value in record.items() :
			if (key * 2 == k and value > 1) :
				#  When element is half of given k
				#  And element appears more than once.
				count += 2
			elif ((k - key in record.keys())) :
				#  When pair of sum k exists
				count += 1
			
		
		if (count > 0) :
			count = int(count / 2)
		
		#  Display given list
		self.printArray(arr, n)
		#  Display calculated result
		print("\n Resultant distinct pair of sum (", 
              k ,") is :  ", count)
	

def main() :
	task = DistinctPairs()
	arr1 = [2, 1, 4, 3, 5, 2, 1, 2, 0]
	arr2 = [4, -2, 2, 3, 4, 7]
	n = len(arr1)
	#  Test A
	k = 4
	#    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	#    sum k = 4   
	#    (2,2) (4, 0) (1, 3)
	#    -------------------
	#    Resultant pair : 3
	task.distinctPairOfKsum(arr1, n, k)
	#  Test B
	#  Get length of arr2
	n = len(arr2)
	k = 5
	#    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	#    sum k = 5   
	#    (-2 + 7) (2 + 3) 
	#    -------------------
	#    Resultant pair : 2
	task.distinctPairOfKsum(arr2, n, k)
	#  Test C
	k = 3
	#    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	#    sum k = 3   
	#    None (no pair of sum 3)
	#    -------------------
	#    Resultant pair : 0
	task.distinctPairOfKsum(arr2, n, k)

if __name__ == "__main__": main()

Output

  2  1  4  3  5  2  1  2  0
 Resultant distinct pair of sum ( 4 ) is :   3
  4  -2  2  3  4  7
 Resultant distinct pair of sum ( 5 ) is :   2
  4  -2  2  3  4  7
 Resultant distinct pair of sum ( 3 ) is :   0
#  Ruby program for
#  Count all distinct pairs with sum equal to k
class DistinctPairs 
	#  Display array elements
	def printArray(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	def distinctPairOfKsum(arr, n, k) 
		count = 0
		#  Use to collect frequency of array elements
		record = Hash.new()
		i = 0
		while (i < n) 
			if (record.key?(arr[i])) 
				#  When key exists then increase the counter frequency
				record[arr[i]] = record[arr[i]] + 1
			else
 
				record[arr[i]] = 1
			end

			i += 1
		end

		record.each { 
            | key, value |
			if (key * 2 == k && value > 1) 
				#  When element is half of given k
				#  And element appears more than once.
				count += 2
			elsif (record.key?(k - key)) 
			#  When pair of sum k exists
			count += 1
		end

		}
		if (count > 0) 
			count = count / 2
		end

		#  Display given array
		self.printArray(arr, n)
		#  Display calculated result
		print("\n Resultant distinct pair of sum (", 
              k ,") is :  ", count, "\n")
	end

end

def main() 
	task = DistinctPairs.new()
	arr1 = [2, 1, 4, 3, 5, 2, 1, 2, 0]
	arr2 = [4, -2, 2, 3, 4, 7]
	n = arr1.length
	#  Test A
	k = 4
	#    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	#    sum k = 4   
	#    (2,2) (4, 0) (1, 3)
	#    -------------------
	#    Resultant pair : 3
	task.distinctPairOfKsum(arr1, n, k)
	#  Test B
	#  Get length of arr2
	n = arr2.length
	k = 5
	#    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	#    sum k = 5   
	#    (-2 + 7) (2 + 3) 
	#    -------------------
	#    Resultant pair : 2
	task.distinctPairOfKsum(arr2, n, k)
	#  Test C
	k = 3
	#    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	#    sum k = 3   
	#    None (no pair of sum 3)
	#    -------------------
	#    Resultant pair : 0
	task.distinctPairOfKsum(arr2, n, k)
end

main()

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0

import scala.collection.mutable._;
// Scala program for
// Count all distinct pairs with sum equal to k
class DistinctPairs()
{
	// Display array elements
	def printArray(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	def distinctPairOfKsum(arr: Array[Int], n: Int, k: Int): Unit = {
		var count: Int = 0;
		// Use to collect frequency of array elements
		var record = Map[Int, Int](); 
		var i: Int = 0;
		while (i < n)
		{
			if (record.contains(arr(i)))
			{
				// When key exists then increase the counter frequency
				record.addOne(arr(i), record.get(arr(i)).get + 1);
			}
			else
			{
				record.addOne(arr(i), 1);
			}
			i += 1;
		}
		for ( (key,value) <- record)
		{
			if (key * 2 == k && value > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.contains(k - key))
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = count / 2;
		}
		// Display given array
		printArray(arr, n);
		// Display calculated result
		println("\n Resultant distinct pair of sum (" + k + ") is :  " + count);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: DistinctPairs = new DistinctPairs();
		var arr1: Array[Int] = Array(2, 1, 4, 3, 5, 2, 1, 2, 0);
		var arr2: Array[Int] = Array(4, -2, 2, 3, 4, 7);
		var n: Int = arr1.length;
		// Test A
		var k: Int = 4;
		/*
		    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
		    sum k = 4   
		    (2,2) (4, 0) (1, 3)
		    -------------------
		    Resultant pair : 3
		        
		*/
		task.distinctPairOfKsum(arr1, n, k);
		// Test B
		// Get length of arr2
		n = arr2.length;
		k = 5;
		/*
		    arr = [  4 , -2 , 2 , 3 , 4 , 7]
		    sum k = 5   
		    (-2 + 7) (2 + 3) 
		    -------------------
		    Resultant pair : 2
		        
		*/
		task.distinctPairOfKsum(arr2, n, k);
		// Test C
		k = 3;
		/*
		    arr = [  4 , -2 , 2 , 3 , 4 , 7]
		    sum k = 3   
		    None (no pair of sum 3)
		    -------------------
		    Resultant pair : 0
		        
		*/
		task.distinctPairOfKsum(arr2, n, k);
	}
}

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
import Foundation;
// Swift 4 program for
// Count all distinct pairs with sum equal to k
class DistinctPairs
{
	// Display array elements
	func printArray(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	func distinctPairOfKsum(_ arr: [Int], _ n: Int, _ k: Int)
	{
		var count: Int = 0;
		// Use to collect frequency of array elements
		var record = [Int : Int]();
		var i: Int = 0;
		while (i < n)
		{
			if (record.keys.contains(arr[i]))
			{
				// When key exists then increase the counter frequency
				record[arr[i]] = record[arr[i]]! + 1;
			}
			else
			{
				record[arr[i]] = 1;
			}
			i += 1;
		}
		for (key, value) in record
		{
			if (key * 2 == k && value > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.keys.contains(k - key))
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = count / 2;
		}
		// Display given array
		self.printArray(arr, n);
		// Display calculated result
		print("\n Resultant distinct pair of sum (", 
              k ,") is :  ", count);
	}
}
func main()
{
	let task: DistinctPairs = DistinctPairs();
	let arr1: [Int] = [2, 1, 4, 3, 5, 2, 1, 2, 0];
	let arr2: [Int] = [4, -2, 2, 3, 4, 7];
	var n: Int = arr1.count;
	// Test A
	var k: Int = 4;
	/*
	    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	    sum k = 4   
	    (2,2) (4, 0) (1, 3)
	    -------------------
	    Resultant pair : 3
	        
	*/
	task.distinctPairOfKsum(arr1, n, k);
	// Test B
	// Get length of arr2
	n = arr2.count;
	k = 5;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 5   
	    (-2 + 7) (2 + 3) 
	    -------------------
	    Resultant pair : 2
	        
	*/
	task.distinctPairOfKsum(arr2, n, k);
	// Test C
	k = 3;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 3   
	    None (no pair of sum 3)
	    -------------------
	    Resultant pair : 0
	        
	*/
	task.distinctPairOfKsum(arr2, n, k);
}
main();

Output

  2  1  4  3  5  2  1  2  0
 Resultant distinct pair of sum ( 4 ) is :   3
  4  -2  2  3  4  7
 Resultant distinct pair of sum ( 5 ) is :   2
  4  -2  2  3  4  7
 Resultant distinct pair of sum ( 3 ) is :   0
// Kotlin program for
// Count all distinct pairs with sum equal to k
class DistinctPairs
{
	// Display array elements
	fun printArray(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	fun distinctPairOfKsum(arr: Array < Int > , n: Int, k: Int): Unit
	{
		var count: Int = 0;
		// Use to collect frequency of array elements
		var record = mutableMapOf < Int, Int > ();
		var i: Int = 0;
		while (i < n)
		{
			if (record.containsKey(arr[i]))
			{
				// When key exists then increase the counter frequency
				record.put(arr[i], record.getValue(arr[i]) + 1);
			}
			else
			{
				record.put(arr[i], 1);
			}
			i += 1;
		}
		for ((key, value) in record)
		{
			if (key * 2 == k && value > 1)
			{
				// When element is half of given k
				// And element appears more than once.
				count += 2;
			}
			else if (record.containsKey(k - key))
			{
				// When pair of sum k exists
				count += 1;
			}
		}
		if (count > 0)
		{
			count = count / 2;
		}
		// Display given array
		this.printArray(arr, n);
		// Display calculated result
		println("\n Resultant distinct pair of sum (" + 
                k + ") is :  " + count);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: DistinctPairs = DistinctPairs();
	val arr1: Array < Int > = arrayOf(2, 1, 4, 3, 5, 2, 1, 2, 0);
	val arr2: Array < Int > = arrayOf(4, -2, 2, 3, 4, 7);
	var n: Int = arr1.count();
	// Test A
	var k: Int = 4;
	/*
	    arr = [ 2 , 1 , 4 , 3 , 5 , 2 , 1 , 2 , 0]
	    sum k = 4   
	    (2,2) (4, 0) (1, 3)
	    -------------------
	    Resultant pair : 3
	        
	*/
	task.distinctPairOfKsum(arr1, n, k);
	// Test B
	// Get length of arr2
	n = arr2.count();
	k = 5;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 5   
	    (-2 + 7) (2 + 3) 
	    -------------------
	    Resultant pair : 2
	        
	*/
	task.distinctPairOfKsum(arr2, n, k);
	// Test C
	k = 3;
	/*
	    arr = [  4 , -2 , 2 , 3 , 4 , 7]
	    sum k = 3   
	    None (no pair of sum 3)
	    -------------------
	    Resultant pair : 0
	        
	*/
	task.distinctPairOfKsum(arr2, n, k);
}

Output

 2 1 4 3 5 2 1 2 0
 Resultant distinct pair of sum (4) is :  3
 4 -2 2 3 4 7
 Resultant distinct pair of sum (5) is :  2
 4 -2 2 3 4 7
 Resultant distinct pair of sum (3) is :  0
Last updated on by Kalkicode




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