Dada una array A que contiene N enteros no negativos. Solo se puede realizar la siguiente operación en el arreglo:
A[i] = ( A[i] + 1 ) % 3
donde A[i] es el elemento del arreglo A en el índice i, y realizar esta operación una vez cuesta 1 unidad. Encuentre el costo mínimo para hacer que todos los elementos sean iguales.
Ejemplos:
Input : 1 0 3 2
Output : 4 units
Explanation: First 3 is converted to 1(3 + 1 % 3 = 1).
Then, if we try to make all elements equal to 1, then
converting 0 to 1 will cost "1" and 2 to 1 will cost "2".
Therefore, in total cost=3 + 1(to convert 3 to 1) = 4,
which is minimum.
Input : 98 4 3 1
Output : 6 units
Explanation: 98, 4 and 3 are converted to 0, 2 and 1.
So, now array becomes {0, 2, 1, 1}. If we try to convert
every element in our new array equal to 1, then converting
0 to 1 will cost "1" and 2 to 1 will cost "2". So, total
cost= 3+ 3(conversion of 98, 4 and 3) = 6, which is the minimum cost.
Enfoque : Al principio, intentaremos convertir todos los números mayores que 2 en un número entre 0 y 2. Dado que los números del 0 al 2 no excederán de 2 utilizando la única operación permitida A(i)=(A(i) +1) % 3(No importa cuantas veces hagamos esta operación). Luego fijaremos uno de los 3 valores posibles (0 a 2) y encontraremos el costo de hacer que todos los elementos sean iguales a él.
El costo mínimo de los tres + el costo extra para convertir todos los números mayores que 2 a un número entre 0 y 2 será nuestra respuesta. Un caso especial que debemos ver aquí es si todos los elementos son iguales por defecto (como en una array {7, 7, 7, 7}), entonces nuestra respuesta será cero.
C++
// CPP program to find minimum cost to
// equalize an array with increment under
// modulo 3 operation.
#include <bits/stdc++.h>
using namespace std;
int mincost(int a[], int n)
{
int c = 1;
// loop to check whether all
// elements are equal or not
for (int i = 0; i < n; i++)
if (a[i] == a[i + 1])
c++;
// A special case when all
// elements are equal
if (c == n)
return 0;
// variable that counts total
// numbers greater 2
int x = 0;
// loop to convert all numbers greater
// than 2 to a range between 0 to 2.
for (int i = 0; i < n; i++)
{
if (a[i] > 2) {
// number greater than 2 gets
// converted to a number between 0 to 2.
a[i] = (a[i] + 1) % 3;
x += 1;
}
}
// variables to count 3 possible ways
// to make all elements equal after
// reducing them to range [0, 2]
int c0 = 0, c1 = 0, c2 = 0;
// loop that counts total cost to
// make all elements equal to 0.
for (int i = 0; i < n; i++)
{
if (a[i] == 1) {
// since we will have to use the
// operation 2 times to convert 1 to 0
// (1+1)%3=2 and then (2+1)%3=0
c0 += 2;
}
// here we use it once since (2+1%3=0)
else if (a[i] == 2)
c0 += 1;
}
// loop that counts total cost to
// make all elements equal to 1
for (int i = 0; i < n; i++)
{
// since (2+1%3=0) and (0+1%3=1)
if (a[i] == 2)
c1 += 2;
// since (0+1%3=1)
else if (a[i] == 0)
c1 += 1;
}
// loop that counts total cost
// to make all elements equal to 2
for (int i = 0; i < n; i++) {
// since 0+1%3=1 and 1+1%3=2
if (a[i] == 0)
c2 += 2;
else if (a[i] == 1)
c2 += 1;
}
// finally the one with minimum
// cost will be our answer
return x + min({ c0, c1, c2 });
}
// Driver program to run above function
int main()
{
int a[] = { 98, 4, 3, 1 };
int n = sizeof(a)/sizeof(a[0]);
cout << mincost(a, n)<<" units";
return 0;
}
Java
// Java program to find minimum
// cost to equalize an array
// with increment under
// modulo 3 operation.
import java.io.*;
class GFG
{
// Function to find minimum cost
static int mincost(int a[], int n)
{
int c = 1;
// loop to check whether all
// elements are equal or not
for (int i = 0; i < n - 1; i++)
if (a[i] == a[i + 1])
c++;
// A special case when all
// elements are equal
if (c == n)
return 0;
// variable that counts total
// numbers greater 2
int x = 0;
// loop to convert all numbers
// greater than 2 to a range
// between 0 to 2.
for (int i = 0; i < n - 1; i++)
{
if (a[i] > 2)
{
// number greater than 2
// gets converted to a
// number between 0 to 2.
a[i] = (a[i] + 1) % 3;
x += 1;
}
}
// variables to count 3 possible
// ways to make all elements equal
// after reducing them to range [0, 2]
int c0 = 0, c1 = 0, c2 = 0;
// loop that counts total cost to
// make all elements equal to 0.
for (int i = 0; i < n - 1; i++)
{
if (a[i] == 1)
{
// since we will have to
// use the operation 2
// times to convert 1 to 0
// (1+1)%3=2 and then (2+1)%3=0
c0 += 2;
}
// here we use it
// once since (2+1%3=0)
else if (a[i] == 2)
c0 += 1;
}
// loop that counts total cost to
// make all elements equal to 1
for (int i = 0; i < n - 1; i++)
{
// since (2+1%3=0)
// and (0+1%3=1)
if (a[i] == 2)
c1 += 2;
// since (0+1%3=1)
else if (a[i] == 0)
c1 += 1;
}
// loop that counts total cost
// to make all elements equal to 2
for (int i = 0; i < n - 1; i++)
{
// since 0+1%3=1
// and 1+1%3=2
if (a[i] == 0)
c2 += 2;
else if (a[i] == 1)
c2 += 1;
}
// finally the one with minimum
// cost will be our answer
return x + Math.min(c0,
Math.min(c1, c2));
}
// Driver Code
public static void main (String[] args)
{
int a[] = new int[]{98, 4, 3, 1};
int n = a.length;
System.out.println(mincost(a, n) +
" " + "units");
}
}
// This code is contributed by ajit
Python3
# Python code to illustrate above approach # function to calculate minimum cost def mincost(a, n): # loop to check whether all elements # are equal or not c = 1 for i in range(0, n-1): if (a[i] == a[i + 1]): c += 1 # A special case when all elements # are equal if (c == n): return 0 # loop to count total no of conversion # of numbers greater than 2 to a # number between 0 to 2. x = 0 for i in range(n): if a[i]>2: a[i]=(a[i]+1)% 3 x += 1 # variables to count 3 possible ways # to make all elements equal after # reducing them to range [0, 2] c0 = c1 = c2 = 0 # loop that counts total cost to # make all elements equal to 0. for i in a: if (i == 1): c0+= 2 elif (i == 2): c0+= 1 # loop that counts total cost to # make all elements equal to 1. for i in a: if (i == 0): c1+= 1 elif (i == 2): c1+= 2 # loop that counts total cost to # make all elements equal to 2. for i in a: if (i == 0): c2+= 2 elif (i == 1): c2+= 1 # finally the one with minimum cost # plus the extra cost to convert numbers # greater than 2 will be our answer return min(c1, c2, c0)+x # Driver code n = 4 a = [98, 4, 3, 1] c = 1 print(mincost(a, n), "units")
C#
// C# program to find minimum cost to
// equalize an array with increment
// under modulo 3 operation.
using System;
class GFG {
// Function to find minimum cost
static int mincost(int []a, int n)
{
int c = 1;
// loop to check whether all
// elements are equal or not
for (int i = 0; i < n - 1; i++)
if (a[i] == a[i + 1])
c++;
// A special case when all
// elements are equal
if (c == n)
return 0;
// variable that counts total
// numbers greater 2
int x = 0;
// loop to convert all numbers greater
// than 2 to a range between 0 to 2.
for (int i = 0; i < n - 1; i++)
{
if (a[i] > 2) {
// number greater than 2 gets
// converted to a number
// between 0 to 2.
a[i] = (a[i] + 1) % 3;
x += 1;
}
}
// variables to count 3 possible ways
// to make all elements equal after
// reducing them to range [0, 2]
int c0 = 0, c1 = 0, c2 = 0;
// loop that counts total cost to
// make all elements equal to 0.
for (int i = 0; i < n - 1; i++)
{
if (a[i] == 1)
{
// since we will have to use the
// operation 2 times to convert 1 to 0
// (1+1)%3=2 and then (2+1)%3=0
c0 += 2;
}
// here we use it once since (2+1%3=0)
else if (a[i] == 2)
c0 += 1;
}
// loop that counts total cost to
// make all elements equal to 1
for (int i = 0; i < n - 1; i++)
{
// since (2+1%3=0) and (0+1%3=1)
if (a[i] == 2)
c1 += 2;
// since (0+1%3=1)
else if (a[i] == 0)
c1 += 1;
}
// loop that counts total cost
// to make all elements equal to 2
for (int i = 0; i < n - 1; i++)
{
// since 0+1%3=1 and 1+1%3=2
if (a[i] == 0)
c2 += 2;
else if (a[i] == 1)
c2 += 1;
}
// finally the one with minimum
// cost will be our answer
return x + Math.Min(c0,
Math.Min(c1, c2) );
}
// Driver Code
public static void Main()
{
int []a = new int[]{98, 4, 3, 1};
int n = a.Length;
Console.Write(mincost(a, n) +
" " + "units");
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to find minimum
// cost to equalize an array
// with increment under modulo
// 3 operation.
function mincost($a, $n)
{
$c = 1;
// loop to check whether all
// elements are equal or not
for ($i = 0; $i < $n; $i++)
$c++;
// A special case when all
// elements are equal
if ($c == $n)
return 0;
// variable that counts
// total numbers greater 2
$x = 0;
// loop to convert all
// numbers greater than 2
// to a range between 0 to 2.
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] > 2)
{
// number greater than 2
// gets converted to a
// number between 0 to 2.
$a[$i] = ($a[$i] + 1) % 3;
$x += 1;
}
}
// variables to count 3
// possible ways to make
// all elements equal after
// reducing them to range [0, 2]
$c0 = 0; $c1 = 0; $c2 = 0;
// loop that counts total
// cost to make all elements
// equal to 0.
for ($i = 0; $i < $n; $i++)
{
if ($a[$i] == 1)
{
// since we will have to
// use the operation 2
// times to convert 1 to 0
// (1+1)%3=2 and then (2+1)%3=0
$c0 += 2;
}
// here we use it
// once since (2+1%3=0)
else if ($a[$i] == 2)
$c0 += 1;
}
// loop that counts total
// cost to make all
// elements equal to 1
for ($i = 0; $i < $n; $i++)
{
// since (2+1%3=0) and
// (0+1%3=1)
if ($a[$i] == 2)
$c1 += 2;
// since (0+1%3=1)
else if ($a[$i] == 0)
$c1 += 1;
}
// loop that counts total
// cost to make all
// elements equal to 2
for ($i = 0; $i < $n; $i++)
{
// since 0+1%3=1
// and 1+1%3=2
if ($a[$i] == 0)
$c2 += 2;
else if ($a[$i] == 1)
$c2 += 1;
}
// finally the one with
// minimum cost will
// be our answer
return $x + min($c0, $c1, $c2 );
}
// Driver Code
$a = array(98, 4, 3, 1);
$n = sizeof($a);
echo mincost($a, $n), " units";
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find minimum cost to
// equalize an array with increment under
// modulo 3 operation.
function mincost(a, n)
{
let c = 1;
// Loop to check whether all
// elements are equal or not
for(let i = 0; i < n; i++)
if (a[i] == a[i + 1])
c++;
// A special case when all
// elements are equal
if (c == n)
return 0;
// Variable that counts total
// numbers greater 2
let x = 0;
// Loop to convert all numbers greater
// than 2 to a range between 0 to 2.
for(let i = 0; i < n; i++)
{
if (a[i] > 2)
{
// Number greater than 2 gets
// converted to a number between 0 to 2.
a[i] = (a[i] + 1) % 3;
x += 1;
}
}
// Variables to count 3 possible ways
// to make all elements equal after
// reducing them to range [0, 2]
let c0 = 0, c1 = 0, c2 = 0;
// Loop that counts total cost to
// make all elements equal to 0.
for(let i = 0; i < n; i++)
{
if (a[i] == 1)
{
// Since we will have to use the
// operation 2 times to convert 1 to 0
// (1+1)%3=2 and then (2+1)%3=0
c0 += 2;
}
// Here we use it once since (2+1%3=0)
else if (a[i] == 2)
c0 += 1;
}
// Loop that counts total cost to
// make all elements equal to 1
for(let i = 0; i < n; i++)
{
// Since (2+1%3=0) and (0+1%3=1)
if (a[i] == 2)
c1 += 2;
// Since (0+1%3=1)
else if (a[i] == 0)
c1 += 1;
}
// Loop that counts total cost
// to make all elements equal to 2
for(let i = 0; i < n; i++)
{
// Since 0+1%3=1 and 1+1%3=2
if (a[i] == 0)
c2 += 2;
else if (a[i] == 1)
c2 += 1;
}
// Finally the one with minimum
// cost will be our answer
let y = Math.min(c0, c1);
return x + Math.min(y, c2);
}
// Driver code
let a = [ 98, 4, 3, 1 ];
let n = a.length;
document.write(mincost(a, n) + " units");
// This code is contributed by subham348
</script>
Producción :
6 units
Complejidad de tiempo : O(n)
Complejidad espacial : O(1) ya que se utilizan variables constantes