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 : 6package 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 : 6import 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
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