Skip to main content

Minimum increment operations to make array unique

Here given code implementation process.

import java.util.HashMap;
/*
    Java Program
    Minimum increment operations to make array unique
*/
public class Manipulation
{
	// Returns the maximum value of array
	public int maximum(int []arr, int n)
	{
		int max = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] > max)
			{
				max = arr[i];
			}
		}
		return max;
	}
	// Returns the minimum value of array
	public int minimum(int []arr, int n)
	{
		int min = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] < min)
			{
				min = arr[i];
			}
		}
		return min;
	}
	public void printData(int []arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public void uniqueByMinIncrement(int []arr, int n)
	{
		// Display array elements
		printData(arr, n);
		int min = minimum(arr, n);
		int max = maximum(arr, n);
		int result = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = ((n * (n - 1)) / 2);
		}
		else
		{
			int frequency = 0;
			HashMap < Integer, Integer > record = 
              new HashMap < Integer, Integer > ();
			// Count frequency of array elements
			for (int i = 0; i < n; ++i)
			{
				if (record.containsKey(arr[i]))
				{
					// Increase element frequency
					record.put(arr[i], record.get(arr[i]) + 1);
				}
				else
				{
					// Add new element
					record.put(arr[i], 1);
				}
			}
			// This loop work on distinct element in array
			for (int i = 0; i < n; ++i)
			{
				// Get element frequency
				frequency = record.get(arr[i]);
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					int distance = arr[i] + 1;
					while (distance < max + n)
					{
						if (record.containsKey(distance) == false)
						{
							result = result + (distance - arr[i]);
							// Add new element into record
							record.put(distance, 1);
							break;
						}
						distance++;
					}
					frequency--;
				}
				record.put(arr[i], 1);
			}
		}
		System.out.println("\nResult : " + result);
	}
	public static void main(String[] args)
	{
		Manipulation task = new Manipulation();
		int[] arr1 = {
			1 , 1 , 1
		};
		int[] arr2 = {
			6 , 5 , 4 , 9 , 2 , 9 , 4 , 3 , 6
		};
		// Case A
		// Get number of elements
		int n = arr1.length;
		// input {1, 1, 1} 
		//           +  +   
		//           1  2   Increment
		//        ↆ  ↆ  ↆ 
		//       {1, 2, 3} 
		//     Result (1 + 2 )
		task.uniqueByMinIncrement(arr1, n);
		// Case B
		// Get number of elements
		n = arr2.length;
		// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
		//        +      +   +         
		//        1      4   1            
		//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
		//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
		//  Result (1+4+1) = 6
		task.uniqueByMinIncrement(arr2, n);
	}
}

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
// Include header file
#include <iostream>
#include <unordered_map>
using namespace std;
/*
    C++ Program
    Minimum increment operations to make array unique
*/
class Manipulation
{
	public:
		// Returns the maximum value of array
		int maximum(int arr[], int n)
		{
			int max = arr[0];
			for (int i = 1; i < n; i++)
			{
				if (arr[i] > max)
				{
					max = arr[i];
				}
			}
			return max;
		}
	// Returns the minimum value of array
	int minimum(int arr[], int n)
	{
		int min = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] < min)
			{
				min = arr[i];
			}
		}
		return min;
	}
	void printData(int arr[], int n)
	{
		for (int i = 0; i < n; ++i)
		{
			cout << " " << arr[i];
		}
	}
	void uniqueByMinIncrement(int arr[], int n)
	{
		// Display array elements
		this->printData(arr, n);
		int min = this->minimum(arr, n);
		int max = this->maximum(arr, n);
		int result = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = ((n *(n - 1)) / 2);
		}
		else
		{
			int frequency = 0;
			unordered_map < int, int > record;
			// Count frequency of array elements
			for (int i = 0; i < n; ++i)
			{
				if (record.find(arr[i]) != record.end())
				{
					// Increase element frequency
					record[arr[i]] = record[arr[i]] + 1;
				}
				else
				{
					// Add new element
					record[arr[i]] = 1;
				}
			}
			// This loop work on distinct element in array
			for (int i = 0; i < n; ++i)
			{
				// Get element frequency
				frequency = record[arr[i]];
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					int distance = arr[i] + 1;
					while (distance < max + n)
					{
						if (record.find(distance) == record.end())
						{
							result = result + (distance - arr[i]);
							// Add new element into record
							record[distance] = 1;
							break;
						}
						distance++;
					}
					frequency--;
				}
				record[arr[i]] = 1;
			}
		}
		cout << "\nResult : " << result << endl;
	}
};
int main()
{
	Manipulation *task = new Manipulation();
	int arr1[] = {
		1 , 1 , 1
	};
	int arr2[] = {
		6 , 5 , 4 , 9 , 2 , 9 , 4 , 3 , 6
	};
	// Case A
	// Get number of elements
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// input {1, 1, 1} 
	//           +  +   
	//           1  2   Increment
	//        ↆ  ↆ  ↆ 
	//       {1, 2, 3} 
	//     Result (1 + 2 )
	task->uniqueByMinIncrement(arr1, n);
	// Case B
	// Get number of elements
	n = sizeof(arr2) / sizeof(arr2[0]);
	// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
	//        +      +   +         
	//        1      4   1            
	//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
	//  Result (1+4+1) = 6
	task->uniqueByMinIncrement(arr2, n);
	return 0;
}

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
package main
import "fmt"
/*
    Go Program
    Minimum increment operations to make array unique
*/

// Returns the maximum value of array
func maximum(arr[] int, n int) int {
	var max int = arr[0]
	for i := 1 ; i < n ; i++ {
		if arr[i] > max {
			max = arr[i]
		}
	}
	return max
}
// Returns the minimum value of array
func minimum(arr[] int, n int) int {
	var min int = arr[0]
	for i := 1 ; i < n ; i++ {
		if arr[i] < min {
			min = arr[i]
		}
	}
	return min
}
func printData(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
func uniqueByMinIncrement(arr[] int, n int) {
	// Display array elements
	printData(arr, n)
	var min int = minimum(arr, n)
	var max int = maximum(arr, n)
	var result int = 0
	if min == max {
		// Best case when all elements are same
		result = ((n * (n - 1)) / 2)
	} else {
		var frequency int = 0
		var record = make(map[int] int)
		// Count frequency of array elements
		for i := 0 ; i < n ; i++ {
			if _, found := record[arr[i]] ; found {
				// Increase element frequency
				record[arr[i]] = record[arr[i]] + 1
			} else {
				// Add new element
				record[arr[i]] = 1
			}
		}
		// This loop work on distinct element in array
		for i := 0 ; i < n ; i++ {
			// Get element frequency
			frequency = record[arr[i]]
			for (frequency > 1) {
				// When frequency of key is more than 1
				var distance int = arr[i] + 1
				for (distance < max + n) {
					if _, found := record[distance] ; found == false {
						result = result + (distance - arr[i])
						// Add new element into record
						record[distance] = 1
						break
					}
					distance++
				}
				frequency--
			}
			record[arr[i]] = 1
		}
	}
	fmt.Println("\nResult : ", result)
}
func main() {

	var arr1 = [] int {
		1,
		1,
		1,
	}
	var arr2 = [] int {
		6,
		5,
		4,
		9,
		2,
		9,
		4,
		3,
		6,
	}
	// Case A
	// Get number of elements
	var n int = len(arr1)
	// input {1, 1, 1} 
	//           +  +   
	//           1  2   Increment
	//        ↆ  ↆ  ↆ 
	//       {1, 2, 3} 
	//     Result (1 + 2 )
	uniqueByMinIncrement(arr1, n)
	// Case B
	// Get number of elements
	n = len(arr2)
	// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
	//        +      +   +         
	//        1      4   1            
	//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
	//  Result (1+4+1) = 6
	uniqueByMinIncrement(arr2, n)
}

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program
    Minimum increment operations to make array unique
*/
public class Manipulation
{
	// Returns the maximum value of array
	public int maximum(int[] arr, int n)
	{
		int max = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] > max)
			{
				max = arr[i];
			}
		}
		return max;
	}
	// Returns the minimum value of array
	public int minimum(int[] arr, int n)
	{
		int min = arr[0];
		for (int i = 1; i < n; i++)
		{
			if (arr[i] < min)
			{
				min = arr[i];
			}
		}
		return min;
	}
	public void printData(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public void uniqueByMinIncrement(int[] arr, int n)
	{
		// Display array elements
		this.printData(arr, n);
		int min = this.minimum(arr, n);
		int max = this.maximum(arr, n);
		int result = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = ((n * (n - 1)) / 2);
		}
		else
		{
			int frequency = 0;
			Dictionary < int, int > record = new Dictionary < int, int > ();
			// Count frequency of array elements
			for (int i = 0; i < n; ++i)
			{
				if (record.ContainsKey(arr[i]))
				{
					// Increase element frequency
					record[arr[i]] = record[arr[i]] + 1;
				}
				else
				{
					// Add new element
					record.Add(arr[i], 1);
				}
			}
			// This loop work on distinct element in array
			for (int i = 0; i < n; ++i)
			{
				// Get element frequency
				frequency = record[arr[i]];
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					int distance = arr[i] + 1;
					while (distance < max + n)
					{
						if (record.ContainsKey(distance) == false)
						{
							result = result + (distance - arr[i]);
							// Add new element into record
							record.Add(distance, 1);
							break;
						}
						distance++;
					}
					frequency--;
				}
				record[arr[i]] = 1;
			}
		}
		Console.WriteLine("\nResult : " + result);
	}
	public static void Main(String[] args)
	{
		Manipulation task = new Manipulation();
		int[] arr1 = {
			1 , 1 , 1
		};
		int[] arr2 = {
			6 , 5 , 4 , 9 , 2 , 9 , 4 , 3 , 6
		};
		// Case A
		// Get number of elements
		int n = arr1.Length;
		// input {1, 1, 1} 
		//           +  +   
		//           1  2   Increment
		//        ↆ  ↆ  ↆ 
		//       {1, 2, 3} 
		//     Result (1 + 2 )
		task.uniqueByMinIncrement(arr1, n);
		// Case B
		// Get number of elements
		n = arr2.Length;
		// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
		//        +      +   +         
		//        1      4   1            
		//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
		//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
		//  Result (1+4+1) = 6
		task.uniqueByMinIncrement(arr2, n);
	}
}

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
<?php
/*
    Php Program
    Minimum increment operations to make array unique
*/
class Manipulation
{
	// Returns the maximum value of array
	public	function maximum($arr, $n)
	{
		$max = $arr[0];
		for ($i = 1; $i < $n; $i++)
		{
			if ($arr[$i] > $max)
			{
				$max = $arr[$i];
			}
		}
		return $max;
	}
	// Returns the minimum value of array
	public	function minimum($arr, $n)
	{
		$min = $arr[0];
		for ($i = 1; $i < $n; $i++)
		{
			if ($arr[$i] < $min)
			{
				$min = $arr[$i];
			}
		}
		return $min;
	}
	public	function printData($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	public	function uniqueByMinIncrement($arr, $n)
	{
		// Display array elements
		$this->printData($arr, $n);
		$min = $this->minimum($arr, $n);
		$max = $this->maximum($arr, $n);
		$result = 0;
		if ($min == $max)
		{
			// Best case when all elements are same
			$result = ((int)(($n * ($n - 1)) / 2));
		}
		else
		{
			$frequency = 0;
			$record = array();
			// Count frequency of array elements
			for ($i = 0; $i < $n; ++$i)
			{
				if (array_key_exists($arr[$i], $record))
				{
					// Increase element frequency
					$record[$arr[$i]] = $record[$arr[$i]] + 1;
				}
				else
				{
					// Add new element
					$record[$arr[$i]] = 1;
				}
			}
			// This loop work on distinct element in array
			for ($i = 0; $i < $n; ++$i)
			{
				// Get element frequency
				$frequency = $record[$arr[$i]];
				while ($frequency > 1)
				{
					// When frequency of key is more than 1
					$distance = $arr[$i] + 1;
					while ($distance < $max + $n)
					{
						if (array_key_exists($distance, $record) == false)
						{
							$result = $result + ($distance - $arr[$i]);
							// Add new element into record
							$record[$distance] = 1;
							break;
						}
						$distance++;
					}
					$frequency--;
				}
				$record[$arr[$i]] = 1;
			}
		}
		echo("\nResult : ".$result.
			"\n");
	}
}

function main()
{
	$task = new Manipulation();
	$arr1 = array(1, 1, 1);
	$arr2 = array(6, 5, 4, 9, 2, 9, 4, 3, 6);
	// Case A
	// Get number of elements
	$n = count($arr1);
	// input {1, 1, 1} 
	//           +  +   
	//           1  2   Increment
	//        ↆ  ↆ  ↆ 
	//       {1, 2, 3} 
	//     Result (1 + 2 )
	$task->uniqueByMinIncrement($arr1, $n);
	// Case B
	// Get number of elements
	$n = count($arr2);
	// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
	//        +      +   +         
	//        1      4   1            
	//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
	//  Result (1+4+1) = 6
	$task->uniqueByMinIncrement($arr2, $n);
}
main();

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
/*
    Node JS Program
    Minimum increment operations to make array unique
*/
class Manipulation
{
	// Returns the maximum value of array
	maximum(arr, n)
	{
		var max = arr[0];
		for (var i = 1; i < n; i++)
		{
			if (arr[i] > max)
			{
				max = arr[i];
			}
		}
		return max;
	}
	// Returns the minimum value of array
	minimum(arr, n)
	{
		var min = arr[0];
		for (var i = 1; i < n; i++)
		{
			if (arr[i] < min)
			{
				min = arr[i];
			}
		}
		return min;
	}
	printData(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	uniqueByMinIncrement(arr, n)
	{
		// Display array elements
		this.printData(arr, n);
		var min = this.minimum(arr, n);
		var max = this.maximum(arr, n);
		var result = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = (parseInt((n * (n - 1)) / 2));
		}
		else
		{
			var frequency = 0;
			var record = new Map();
			// Count frequency of array elements
			for (var i = 0; i < n; ++i)
			{
				if (record.has(arr[i]))
				{
					// Increase element frequency
					record.set(arr[i], record.get(arr[i]) + 1);
				}
				else
				{
					// Add new element
					record.set(arr[i], 1);
				}
			}
			// This loop work on distinct element in array
			for (var i = 0; i < n; ++i)
			{
				// Get element frequency
				frequency = record.get(arr[i]);
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					var distance = arr[i] + 1;
					while (distance < max + n)
					{
						if (record.has(distance) == false)
						{
							result = result + (distance - arr[i]);
							// Add new element into record
							record.set(distance, 1);
							break;
						}
						distance++;
					}
					frequency--;
				}
				record.set(arr[i], 1);
			}
		}
		console.log("\nResult : " + result);
	}
}

function main()
{
	var task = new Manipulation();
	var arr1 = [1, 1, 1];
	var arr2 = [6, 5, 4, 9, 2, 9, 4, 3, 6];
	// Case A
	// Get number of elements
	var n = arr1.length;
	// input {1, 1, 1} 
	//           +  +   
	//           1  2   Increment
	//        ↆ  ↆ  ↆ 
	//       {1, 2, 3} 
	//     Result (1 + 2 )
	task.uniqueByMinIncrement(arr1, n);
	// Case B
	// Get number of elements
	n = arr2.length;
	// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
	//        +      +   +         
	//        1      4   1            
	//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
	//  Result (1+4+1) = 6
	task.uniqueByMinIncrement(arr2, n);
}
main();

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
#    Python 3 Program
#    Minimum increment operations to make array unique
class Manipulation :
	#  Returns the maximum value of list
	def maximum(self, arr, n) :
		max = arr[0]
		i = 1
		while (i < n) :
			if (arr[i] > max) :
				max = arr[i]
			
			i += 1
		
		return max
	
	#  Returns the minimum value of list
	def minimum(self, arr, n) :
		min = arr[0]
		i = 1
		while (i < n) :
			if (arr[i] < min) :
				min = arr[i]
			
			i += 1
		
		return min
	
	def printData(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	def uniqueByMinIncrement(self, arr, n) :
		#  Display list elements
		self.printData(arr, n)
		min = self.minimum(arr, n)
		max = self.maximum(arr, n)
		result = 0
		if (min == max) :
			#  Best case when all elements are same
			result = (int((n * (n - 1)) / 2))
		else :
			frequency = 0
			record = dict()
			i = 0
			#  Count frequency of list elements
			while (i < n) :
				if ((arr[i] in record.keys())) :
					#  Increase element frequency
					record[arr[i]] = record.get(arr[i]) + 1
				else :
					#  Add new element
					record[arr[i]] = 1
				
				i += 1
			
			i = 0
			#  This loop work on distinct element in list
			while (i < n) :
				#  Get element frequency
				frequency = record.get(arr[i])
				while (frequency > 1) :
					#  When frequency of key is more than 1
					distance = arr[i] + 1
					while (distance < max + n) :
						if ((distance in record.keys()) == False) :
							result = result + (distance - arr[i])
							#  Add new element into record
							record[distance] = 1
							break
						
						distance += 1
					
					frequency -= 1
				
				record[arr[i]] = 1
				i += 1
			
		
		print("\nResult : ", result)
	

def main() :
	task = Manipulation()
	arr1 = [1, 1, 1]
	arr2 = [6, 5, 4, 9, 2, 9, 4, 3, 6]
	#  Case A
	#  Get number of elements
	n = len(arr1)
	#  input :1, 1, 1 
	#            +  +   
	#            1  2   Increment
	#         ↆ  ↆ  ↆ 
	#        :1, 2, 3 
	#      Result (1 + 2 )
	task.uniqueByMinIncrement(arr1, n)
	#  Case B
	#  Get number of elements
	n = len(arr2)
	#  input :6, 5,  4,  9, 2, 9, 4, 3, 6 
	#         +      +   +         
	#         1      4   1            
	#         ↆ  ↆ   ↆ   ↆ   ↆ  ↆ  ↆ  ↆ  ↆ
	#        :7, 5,  8, 10, 2, 9, 4, 3, 6 
	#   Result (1+4+1) = 6
	task.uniqueByMinIncrement(arr2, n)

if __name__ == "__main__": main()

input

  1  1  1
Result :  3
  6  5  4  9  2  9  4  3  6
Result :  6
#    Ruby Program
#    Minimum increment operations to make array unique
class Manipulation 
	#  Returns the maximum value of array
	def maximum(arr, n) 
		max = arr[0]
		i = 1
		while (i < n) 
			if (arr[i] > max) 
				max = arr[i]
			end

			i += 1
		end

		return max
	end

	#  Returns the minimum value of array
	def minimum(arr, n) 
		min = arr[0]
		i = 1
		while (i < n) 
			if (arr[i] < min) 
				min = arr[i]
			end

			i += 1
		end

		return min
	end

	def printData(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	def uniqueByMinIncrement(arr, n) 
		#  Display array elements
		self.printData(arr, n)
		min = self.minimum(arr, n)
		max = self.maximum(arr, n)
		result = 0
		if (min == max) 
			#  Best case when all elements are same
			result = ((n * (n - 1)) / 2)
		else
 
			frequency = 0
			record = Hash.new()
			i = 0
			#  Count frequency of array elements
			while (i < n) 
				if (record.key?(arr[i])) 
					#  Increase element frequency
					record[arr[i]] = record[arr[i]] + 1
				else
 
					#  Add new element
					record[arr[i]] = 1
				end

				i += 1
			end

			i = 0
			#  This loop work on distinct element in array
			while (i < n) 
				#  Get element frequency
				frequency = record[arr[i]]
				while (frequency > 1) 
					#  When frequency of key is more than 1
					distance = arr[i] + 1
					while (distance < max + n) 
						if (record.key?(distance) == false) 
							result = result + (distance - arr[i])
							#  Add new element into record
							record[distance] = 1
							break
						end

						distance += 1
					end

					frequency -= 1
				end

				record[arr[i]] = 1
				i += 1
			end

		end

		print("\nResult : ", result, "\n")
	end

end

def main() 
	task = Manipulation.new()
	arr1 = [1, 1, 1]
	arr2 = [6, 5, 4, 9, 2, 9, 4, 3, 6]
	#  Case A
	#  Get number of elements
	n = arr1.length
	#  input 1, 1, 1end
	#           +  +   
	#           1  2   Increment
	#        ↆ  ↆ  ↆ 
	#        1, 2, 3
	#      Result (1 + 2 )
	task.uniqueByMinIncrement(arr1, n)
	#  Case B
	#  Get number of elements
	n = arr2.length
	#  input 6, 5,  4,  9, 2, 9, 4, 3, 6
	#         +      +   +         
	#         1      4   1            
	#         ↆ  ↆ   ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	#         7, 5,  8, 10, 2, 9, 4, 3, 6
	#   Result (1+4+1) = 6
	task.uniqueByMinIncrement(arr2, n)
end

main()

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
import scala.collection.mutable._;
/*
    Scala Program
    Minimum increment operations to make array unique
*/
class Manipulation()
{
	// Returns the maximum value of array
	def maximum(arr: Array[Int], n: Int): Int = {
		var max: Int = arr(0);
		var i: Int = 1;
		while (i < n)
		{
			if (arr(i) > max)
			{
				max = arr(i);
			}
			i += 1;
		}
		return max;
	}
	// Returns the minimum value of array
	def minimum(arr: Array[Int], n: Int): Int = {
		var min: Int = arr(0);
		var i: Int = 1;
		while (i < n)
		{
			if (arr(i) < min)
			{
				min = arr(i);
			}
			i += 1;
		}
		return min;
	}
	def printData(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	def uniqueByMinIncrement(arr: Array[Int], n: Int): Unit = {
		// Display array elements
		printData(arr, n);
		var min: Int = minimum(arr, n);
		var max: Int = maximum(arr, n);
		var result: Int = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = ((n * (n - 1)) / 2);
		}
		else
		{
			var frequency: Int = 0;
			var record: HashMap[Int, Int] = new HashMap[Int, Int]();
			var i: Int = 0;
			// Count frequency of array elements
			while (i < n)
			{
				if (record.contains(arr(i)))
				{
					// Increase element frequency
					record.addOne(arr(i), record.get(arr(i)).get + 1);
				}
				else
				{
					// Add new element
					record.addOne(arr(i), 1);
				}
				i += 1;
			}
			i = 0;
			// This loop work on distinct element in array
			while (i < n)
			{
				// Get element frequency
				frequency = record.get(arr(i)).get;
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					var distance: Int = arr(i) + 1;
					while (distance < max + n)
					{
						if (record.contains(distance) == false)
						{
							result = result + (distance - arr(i));
							// Add new element into record
							record.addOne(distance, 1);
							distance = max + n;
						}
						distance += 1;
					}
					frequency -= 1;
				}
				record.addOne(arr(i), 1);
				i += 1;
			}
		}
		println("\nResult : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Manipulation = new Manipulation();
		var arr1: Array[Int] = Array(1, 1, 1);
		var arr2: Array[Int] = Array(6, 5, 4, 9, 2, 9, 4, 3, 6);
		// Case A
		// Get number of elements
		var n: Int = arr1.length;
		// input {1, 1, 1} 
		//           +  +   
		//           1  2   Increment
		//        ↆ  ↆ  ↆ 
		//       {1, 2, 3} 
		//     Result (1 + 2 )
		task.uniqueByMinIncrement(arr1, n);
		// Case B
		// Get number of elements
		n = arr2.length;
		// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
		//        +      +   +         
		//        1      4   1            
		//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
		//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
		//  Result (1+4+1) = 6
		task.uniqueByMinIncrement(arr2, n);
	}
}

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6
import Foundation;
/*
    Swift 4 Program
    Minimum increment operations to make array unique
*/
class Manipulation
{
	// Returns the maximum value of array
	func maximum(_ arr: [Int], _ n: Int) -> Int
	{
		var max: Int = arr[0];
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i] > max)
			{
				max = arr[i];
			}
			i += 1;
		}
		return max;
	}
	// Returns the minimum value of array
	func minimum(_ arr: [Int], _ n: Int) -> Int
	{
		var min: Int = arr[0];
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i] < min)
			{
				min = arr[i];
			}
			i += 1;
		}
		return min;
	}
	func printData(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	func uniqueByMinIncrement(_ arr: [Int], _ n: Int)
	{
		// Display array elements
		self.printData(arr, n);
		let min: Int = self.minimum(arr, n);
		let max: Int = self.maximum(arr, n);
		var result: Int = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = ((n * (n - 1)) / 2);
		}
		else
		{
			var frequency: Int = 0;
			var record = [Int : Int]();
			var i: Int = 0;
			// Count frequency of array elements
			while (i < n)
			{
				if (record.keys.contains(arr[i]))
				{
					// Increase element frequency
					record[arr[i]] = record[arr[i]]! + 1;
				}
				else
				{
					// Add new element
					record[arr[i]] = 1;
				}
				i += 1;
			}
			i = 0;
			// This loop work on distinct element in array
			while (i < n)
			{
				// Get element frequency
				frequency = record[arr[i]]!;
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					var distance: Int = arr[i] + 1;
					while (distance < max + n)
					{
						if (record.keys.contains(distance) == false)
						{
							result = result + (distance - arr[i]);
							// Add new element into record
							record[distance] = 1;
							break;
						}
						distance += 1;
					}
					frequency -= 1;
				}
				record[arr[i]] = 1;
				i += 1;
			}
		}
		print("\nResult : ", result);
	}
}
func main()
{
	let task: Manipulation = Manipulation();
	let arr1: [Int] = [1, 1, 1];
	let arr2: [Int] = [6, 5, 4, 9, 2, 9, 4, 3, 6];
	// Case A
	// Get number of elements
	var n: Int = arr1.count;
	// input {1, 1, 1} 
	//           +  +   
	//           1  2   Increment
	//        ↆ  ↆ  ↆ 
	//       {1, 2, 3} 
	//     Result (1 + 2 )
	task.uniqueByMinIncrement(arr1, n);
	// Case B
	// Get number of elements
	n = arr2.count;
	// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
	//        +      +   +         
	//        1      4   1            
	//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
	//  Result (1+4+1) = 6
	task.uniqueByMinIncrement(arr2, n);
}
main();

input

  1  1  1
Result :  3
  6  5  4  9  2  9  4  3  6
Result :  6
/*
    Kotlin Program
    Minimum increment operations to make array unique
*/
class Manipulation
{
	// Returns the maximum value of array
	fun maximum(arr: Array < Int > , n: Int): Int
	{
		var max: Int = arr[0];
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i] > max)
			{
				max = arr[i];
			}
			i += 1;
		}
		return max;
	}
	// Returns the minimum value of array
	fun minimum(arr: Array < Int > , n: Int): Int
	{
		var min: Int = arr[0];
		var i: Int = 1;
		while (i < n)
		{
			if (arr[i] < min)
			{
				min = arr[i];
			}
			i += 1;
		}
		return min;
	}
	fun printData(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	fun uniqueByMinIncrement(arr: Array < Int > , n: Int): Unit
	{
		// Display array elements
		this.printData(arr, n);
		val min: Int = this.minimum(arr, n);
		val max: Int = this.maximum(arr, n);
		var result: Int = 0;
		if (min == max)
		{
			// Best case when all elements are same
			result = ((n * (n - 1)) / 2);
		}
		else
		{
			var frequency: Int ;
			val record: HashMap < Int, Int > = HashMap < Int, Int > ();
			var i: Int = 0;
			// Count frequency of array elements
			while (i < n)
			{
				if (record.containsKey(arr[i]))
				{
					// Increase element frequency
					record.put(arr[i], record.getValue(arr[i]) + 1);
				}
				else
				{
					// Add new element
					record.put(arr[i], 1);
				}
				i += 1;
			}
			i = 0;
			// This loop work on distinct element in array
			while (i < n)
			{
				// Get element frequency
				frequency = record.getValue(arr[i]);
				while (frequency > 1)
				{
					// When frequency of key is more than 1
					var distance: Int = arr[i] + 1;
					while (distance < max + n)
					{
						if (record.containsKey(distance) == false)
						{
							result = result + (distance - arr[i]);
							// Add new element into record
							record.put(distance, 1);
							break;
						}
						distance += 1;
					}
					frequency -= 1;
				}
				record.put(arr[i], 1);
				i += 1;
			}
		}
		println("\nResult : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Manipulation = Manipulation();
	val arr1: Array < Int > = arrayOf(1, 1, 1);
	val arr2: Array < Int > = arrayOf(6, 5, 4, 9, 2, 9, 4, 3, 6);
	// Case A
	// Get number of elements
	var n: Int = arr1.count();
	// input {1, 1, 1} 
	//           +  +   
	//           1  2   Increment
	//        ↆ  ↆ  ↆ 
	//       {1, 2, 3} 
	//     Result (1 + 2 )
	task.uniqueByMinIncrement(arr1, n);
	// Case B
	// Get number of elements
	n = arr2.count();
	// input {6, 5,  4,  9, 2, 9, 4, 3, 6} 
	//        +      +   +         
	//        1      4   1            
	//        ↆ  ↆ    ↆ   ↆ  ↆ  ↆ  ↆ   ↆ  ↆ
	//       {7, 5,  8, 10, 2, 9, 4, 3, 6} 
	//  Result (1+4+1) = 6
	task.uniqueByMinIncrement(arr2, n);
}

input

 1 1 1
Result : 3
 6 5 4 9 2 9 4 3 6
Result : 6




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