Dada una array de enteros ordenados. Necesitamos hacer que los elementos de la array sean distintos aumentando los valores y manteniendo la suma de la array al mínimo posible. Necesitamos imprimir la suma mínima posible como salida.
Ejemplos:
Input : arr[] = { 2, 2, 3, 5, 6 } ;
Output : 20
Explanation : We make the array as {2,
3, 4, 5, 6}. Sum becomes 2 + 3 + 4 +
5 + 6 = 20
Input : arr[] = { 20, 20 } ;
Output : 41
Explanation : We make {20, 21}
Input : arr[] = { 3, 4, 6, 8 };
Output : 21
Explanation : All elements are unique
so result is sum of each elements.
Método 1:
1. Recorra cada elemento de la array.
2. si arr[i] == arr[i-1] entonces actualice cada elemento de la array agregando 1 desde la i-ésima posición (actual) hasta donde el elemento es igual a su elemento anterior o se ha vuelto menor que el anterior (porque anterior se incrementó).
3. Después de atravesar cada elemento, devuelva la suma.
C++
// CPP program to make sorted array elements
// distinct by incrementing elements and keeping
// sum to minimum.
#include <iostream>
using namespace std;
// To find minimum sum of unique elements.
int minSum(int arr[], int n)
{
int sum = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1]) {
// While current element is same as
// previous or has become smaller
// than previous.
int j = i;
while (j < n && arr[j] <= arr[j - 1]) {
arr[j] = arr[j] + 1;
j++;
}
}
sum = sum + arr[i];
}
return sum;
}
// Driver code
int main()
{
int arr[] = { 2, 2, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minSum(arr, n) << endl;
return 0;
}
Java
// Java program to make sorted
// array elements distinct by
// incrementing elements and
// keeping sum to minimum.
import java.io.*;
class GFG
{
// To find minimum sum
// of unique elements.
static int minSum(int arr[], int n)
{
int sum = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] == arr[i - 1]) {
// While current element is same as
// previous or has become smaller
// than previous.
int j = i;
while (j < n && arr[j] <= arr[j - 1])
{
arr[j] = arr[j] + 1;
j++;
}
}
sum = sum + arr[i];
}
return sum;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 2, 3, 5, 6 };
int n = arr.length;
System.out.println(minSum(arr, n));
}
}
// This code is contributed by Ansu Kumari
Python3
# Python3 program to make sorted array elements # distinct by incrementing elements and keeping # sum to minimum. # To find minimum sum of unique elements. def minSum(arr, n): sm = arr[0] for i in range(1, n): if arr[i] == arr[i - 1]: # While current element is same as # previous or has become smaller # than previous. j = i while j < n and arr[j] <= arr[j - 1]: arr[j] = arr[j] + 1 j += 1 sm = sm + arr[i] return sm # Driver code arr = [ 2, 2, 3, 5, 6 ] n = len(arr) print(minSum(arr, n)) # This code is contributed by Ansu Kumari
C#
// C# program to make sorted
// array elements distinct by
// incrementing elements and
// keeping sum to minimum.
using System;
class GFG
{
// To find minimum sum
// of unique elements.
static int minSum(int []arr, int n)
{
int sum = arr[0];
for (int i = 1; i < n; i++)
{
if (arr[i] == arr[i - 1]) {
// While current element is same as
// previous or has become smaller
// than previous.
int j = i;
while (j < n && arr[j] <= arr[j - 1])
{
arr[j] = arr[j] + 1;
j++;
}
}
sum = sum + arr[i];
}
return sum;
}
// Driver code
public static void Main ()
{
int []arr = { 2, 2, 3, 5, 6 };
int n = arr.Length;
Console.WriteLine(minSum(arr, n));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to make sorted array
// elements distinct by incrementing
// elements and keeping sum to minimum.
// To find minimum sum of unique
// elements.
function minSum($arr, $n)
{
$sum = $arr[0];
for ($i = 1; $i < $n; $i++) {
if ($arr[$i] == $arr[$i - 1])
{
// While current element is
// same as previous or has
// become smaller than
// previous.
$j = $i;
while ($j < $n && $arr[$j]
<= $arr[$j - 1])
{
$arr[$j] = $arr[$j] + 1;
$j++;
}
}
$sum = $sum + $arr[$i];
}
return $sum;
}
// Driver code
$arr = array ( 2, 2, 3, 5, 6 );
$n = sizeof($arr) ;
echo minSum($arr, $n),"\n";
// This code is contributed by ajit
?>
Javascript
<script>
// JavaScript program to make sorted
// array elements distinct by
// incrementing elements and
// keeping sum to minimum.
// To find minimum sum
// of unique elements.
function minSum(arr, n)
{
let sum = arr[0];
for (let i = 1; i < n; i++)
{
if (arr[i] == arr[i - 1]) {
// While current element is same as
// previous or has become smaller
// than previous.
let j = i;
while (j < n && arr[j] <= arr[j - 1])
{
arr[j] = arr[j] + 1;
j++;
}
}
sum = sum + arr[i];
}
return sum;
}
// Driver code
let arr = [ 2, 2, 3, 5, 6 ];
let n = arr.length;
document.write(minSum(arr, n));
</script>
Producción :
20
Complejidad de tiempo: O (n ^ 2)
Método 2:
1. Recorra cada elemento de la array.
2. Si arr[i] <= prev entonces actualice prev agregando 1 y actualice sum agregando prev, de
lo contrario actualice prev por elemento cur y actualice sum agregando cur element (arr[i]).
3. Después de atravesar cada elemento, devuelva la suma.
C++
// Efficient CPP program to make sorted array
// elements distinct by incrementing elements
// and keeping sum to minimum.
#include <iostream>
using namespace std;
// To find minimum sum of unique elements.
int minSum(int arr[], int n)
{
int sum = arr[0], prev = arr[0];
for (int i = 1; i < n; i++) {
// If violation happens, make current
// value as 1 plus previous value and
// add to sum.
if (arr[i] <= prev) {
prev = prev + 1;
sum = sum + prev;
}
// No violation.
else {
sum = sum + arr[i];
prev = arr[i];
}
}
return sum;
}
// Drivers code
int main()
{
int arr[] = { 2, 2, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minSum(arr, n) << endl;
return 0;
}
Java
// Efficient Java program to make sorted array
// elements distinct by incrementing elements
// and keeping sum to minimum.
import java.io.*;
class GFG {
// To find minimum sum of unique elements.
static int minSum(int arr[], int n)
{
int sum = arr[0], prev = arr[0];
for (int i = 1; i < n; i++) {
// If violation happens, make current
// value as 1 plus previous value and
// add to sum.
if (arr[i] <= prev) {
prev = prev + 1;
sum = sum + prev;
}
// No violation.
else {
sum = sum + arr[i];
prev = arr[i];
}
}
return sum;
}
// Drivers code
public static void main (String[] args) {
int arr[] = { 2, 2, 3, 5, 6 };
int n = arr.length;
System.out.println(minSum(arr, n));
}
}
// This code is contributed by Ansu Kumari.
Python3
# Efficient Python program to make sorted array # elements distinct by incrementing elements # and keeping sum to minimum. # To find minimum sum of unique elements def minSum(arr, n): sum = arr[0]; prev = arr[0] for i in range(1, n): # If violation happens, make current # value as 1 plus previous value and # add to sum. if arr[i] <= prev: prev = prev + 1 sum = sum + prev # No violation. else : sum = sum + arr[i] prev = arr[i] return sum # Drivers code arr = [ 2, 2, 3, 5, 6 ] n = len(arr) print(minSum(arr, n)) # This code is contributed by Ansu Kumari
C#
// Efficient C# program to make sorted array
// elements distinct by incrementing elements
// and keeping sum to minimum.
using System;
class GFG {
// To find minimum sum of unique elements.
static int minSum(int []arr, int n)
{
int sum = arr[0], prev = arr[0];
for (int i = 1; i < n; i++) {
// If violation happens, make current
// value as 1 plus previous value and
// add to sum.
if (arr[i] <= prev) {
prev = prev + 1;
sum = sum + prev;
}
// No violation.
else {
sum = sum + arr[i];
prev = arr[i];
}
}
return sum;
}
// Drivers code
public static void Main () {
int []arr = { 2, 2, 3, 5, 6 };
int n = arr.Length;
Console.WriteLine(minSum(arr, n));
}
}
// This code is contributed by vt_m .
PHP
<?php
// Efficient PHP program to
// make sorted array elements
// distinct by incrementing
// elements and keeping sum
// to minimum.
// To find minimum sum
// of unique elements.
function minSum($arr, $n)
{
$sum = $arr[0];
$prev = $arr[0];
for ( $i = 1; $i < $n; $i++)
{
// If violation happens,
// make current value as
// 1 plus previous value
// and add to sum.
if ($arr[$i] <= $prev)
{
$prev = $prev + 1;
$sum = $sum + $prev;
}
// No violation.
else
{
$sum = $sum + $arr[$i];
$prev = $arr[$i];
}
}
return $sum;
}
// Driver code
$arr = array(2, 2, 3, 5, 6);
$n = count($arr);
echo minSum($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Efficient Javascript program to make sorted array
// elements distinct by incrementing elements
// and keeping sum to minimum.
// To find minimum sum of unique elements.
function minSum(arr, n)
{
let sum = arr[0], prev = arr[0];
for(let i = 1; i < n; i++)
{
// If violation happens, make current
// value as 1 plus previous value and
// add to sum.
if (arr[i] <= prev)
{
prev = prev + 1;
sum = sum + prev;
}
// No violation.
else
{
sum = sum + arr[i];
prev = arr[i];
}
}
return sum;
}
// Driver code
let arr = [ 2, 2, 3, 5, 6 ];
let n = arr.length;
document.write(minSum(arr, n));
// This code is contributed by decode2207
</script>
Producción:
20
Complejidad de tiempo: O(n)