Dada una array de tamaño n , la tarea es encontrar el número mínimo de pasos necesarios para hacer que todos los elementos de la array sean divisibles por 4. Un paso se define como la eliminación de dos elementos cualquiera de la array y la suma de estos elementos. a la array.
Ejemplos:
Entrada: array = {1, 2, 3, 1, 2, 3, 8}
Salida: 3
Explicación:
Como podemos ver en la imagen,
combinar array[0] y array[2] lo convierte en 4. De manera similar , array[1] y array[4] así como array[3] y array[5] . array[6] ya es divisible por 4. Entonces, al hacer 3 pasos, todos los elementos de la array se vuelven divisibles por 4.
Ingrese: array = {12, 31, 47, 32, 93, 24, 61, 29, 21, 34}
Salida: 4
Enfoque: La idea aquí es convertir todos los elementos de la array a módulo 4. Primero, la suma de todos los elementos de la array debe ser divisible por 4. De lo contrario, esta tarea no es posible.
- Inicialice un módulo de array con un tamaño de 4 a 0.
- Inicialice una cuenta de contador a 0 para realizar un seguimiento del número de pasos realizados.
- Recorra la array de entrada y tome el módulo 4 de cada elemento.
- Incremente el valor del valor mod 4 en la array de módulos en 1.
- modulus[0] es el recuento de elementos que ya son divisibles por 4. Por lo tanto, no es necesario emparejarlos con ningún otro elemento.
- Los elementos modulus[1] y modulus[3] se pueden combinar para obtener un número divisible por 4. Por lo tanto, incremente el conteo al valor mínimo de ambos.
- Cada 2 elementos de modulus[2] se pueden combinar para obtener un elemento divisible a 4.
- Para los elementos restantes, incremente el valor modulus[2] a la mitad de modulus[1] y modulus[3] .
- Ahora, incremente el conteo por medio módulo[2] . Tomamos la mitad porque cada dos elementos se combinan como uno.
- El valor final de count es el número de pasos necesarios para convertir todos los elementos de la array de entrada divisible por 4.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
int getSteps(int arr[], int n)
{
// Count to keep track of the
// number of steps done.
int count = 0;
// Modulus array to store all elements mod 4
int modulus[4] = { 0 };
// sum to check if given task is possible
int sum = 0;
// Loop to store all elements mod 4
// and calculate sum;
int i;
for (i = 0; i < n; i++)
{
int mod = arr[i] % 4;
sum += mod;
modulus[mod]++;
}
// If sum is not divisible by 4,
// not possible
if (sum % 4 != 0)
{
return -1;
}
else
{
// Find minimum of modulus[1] and modulus[3]
// and increment the count by the minimum
if (modulus[1] > modulus[3])
{
count += modulus[3];
}
else
{
count += modulus[1];
}
// Update the values in modulus array.
modulus[1] -= count;
modulus[3] -= count;
// Use modulus[2] to pair remaining elements.
modulus[2] += modulus[1] / 2;
modulus[2] += modulus[3] / 2;
// increment count to half of remaining
// modulus[1] or modulus of [3] elements.
count += modulus[1] / 2;
count += modulus[3] / 2;
// increment count by half of modulus[2]
count += modulus[2] / 2;
return count;
}
}
// Driver Code
int main()
{
// size of array
int n = 7;
// input array
int arr[] = { 1, 2, 3, 1, 2, 3, 8 };
int count = getSteps(arr, n);
cout << count;
}
// This code is contributed
// by Akanksha Rai
C
#include <stdio.h>
#include <string.h>
int getSteps(int arr[], int n)
{
// Count to keep track of the number of steps done.
int count = 0;
// Modulus array to store all elements mod 4
int modulus[4] = { 0 };
// sum to check if given task is possible
int sum = 0;
// Loop to store all elements mod 4 and calculate sum;
int i;
for (i = 0; i < n; i++) {
int mod = arr[i] % 4;
sum += mod;
modulus[mod]++;
}
// If sum is not divisible by 4, not possible
if (sum % 4 != 0) {
return -1;
}
else {
// Find minimum of modulus[1] and modulus[3]
// and increment the count by the minimum
if (modulus[1] > modulus[3]) {
count += modulus[3];
}
else {
count += modulus[1];
}
// Update the values in modulus array.
modulus[1] -= count;
modulus[3] -= count;
// Use modulus[2] to pair remaining elements.
modulus[2] += modulus[1] / 2;
modulus[2] += modulus[3] / 2;
// increment count to half of remaining
// modulus[1] or modulus of [3] elements.
count += modulus[1] / 2;
count += modulus[3] / 2;
// increment count by half of modulus[2]
count += modulus[2] / 2;
return count;
}
}
// Driver Code
int main()
{
// size of array
int n = 7;
// input array
int arr[] = { 1, 2, 3, 1, 2, 3, 8 };
int count = getSteps(arr, n);
printf("%d", count);
}
Java
// Java program for the above approach
class GFG
{
static int getSteps(int arr[], int n)
{
// Count to keep track of the number of steps done.
int count = 0;
// Modulus array to store all elements mod 4
int modulus[] = new int[4];
// sum to check if given task is possible
int sum = 0;
// Loop to store all elements
// mod 4 and calculate sum;
int i;
for (i = 0; i < n; i++)
{
int mod = arr[i] % 4;
sum += mod;
modulus[mod]++;
}
// If sum is not divisible by 4, not possible
if (sum % 4 != 0)
{
return -1;
}
else {
// Find minimum of modulus[1] and modulus[3]
// and increment the count by the minimum
if (modulus[1] > modulus[3])
{
count += modulus[3];
}
else
{
count += modulus[1];
}
// Update the values in modulus array.
modulus[1] -= count;
modulus[3] -= count;
// Use modulus[2] to pair remaining elements.
modulus[2] += modulus[1] / 2;
modulus[2] += modulus[3] / 2;
// increment count to half of remaining
// modulus[1] or modulus of [3] elements.
count += modulus[1] / 2;
count += modulus[3] / 2;
// increment count by half of modulus[2]
count += modulus[2] / 2;
return count;
}
}
// Driver Code
public static void main(String[] args)
{
// size of array
int n = 7;
// input array
int arr[] = { 1, 2, 3, 1, 2, 3, 8 };
int count = getSteps(arr, n);
System.out.printf("%d", count);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 program for the above approach def getSteps(arr, n): # Count to keep track of the # number of steps done. count = 0 # Modulus array to store all elements mod 4 modulus = [0 for i in range(4)] # Sum to check if given task is possible Sum = 0 # Loop to store all elements mod 4 # and calculate Sum i = 0 for i in range(n): mod = arr[i] % 4 Sum += mod modulus[mod] += 1 # If Sum is not divisible by 4, # not possible if (Sum % 4 != 0): return -1 else: # Find minimum of modulus[1] and modulus[3] # and increment the count by the minimum if (modulus[1] > modulus[3]): count += modulus[3] else: count += modulus[1] # Update the values in modulus array. modulus[1] -= count modulus[3] -= count # Use modulus[2] to pair remaining elements. modulus[2] += modulus[1] // 2 modulus[2] += modulus[3] // 2 # increment count to half of remaining # modulus[1] or modulus of [3] elements. count += modulus[1] // 2 count += modulus[3] // 2 # increment count by half of modulus[2] count += modulus[2] // 2 return count # Driver Code # size of array n = 7 # input array arr = [1, 2, 3, 1, 2, 3, 8] count = getSteps(arr, n) print(count) # This code is contributed by mohit kumar
C#
// C# program for the above approach
using System;
class GFG
{
static int getSteps(int []arr, int n)
{
// Count to keep track of the number of steps done.
int count = 0;
// Modulus array to store all elements mod 4
int []modulus = new int[4];
// sum to check if given task is possible
int sum = 0;
// Loop to store all elements
// mod 4 and calculate sum;
int i;
for (i = 0; i < n; i++)
{
int mod = arr[i] % 4;
sum += mod;
modulus[mod]++;
}
// If sum is not divisible by 4, not possible
if (sum % 4 != 0)
{
return -1;
}
else
{
// Find minimum of modulus[1] and modulus[3]
// and increment the count by the minimum
if (modulus[1] > modulus[3])
{
count += modulus[3];
}
else
{
count += modulus[1];
}
// Update the values in modulus array.
modulus[1] -= count;
modulus[3] -= count;
// Use modulus[2] to pair remaining elements.
modulus[2] += modulus[1] / 2;
modulus[2] += modulus[3] / 2;
// increment count to half of remaining
// modulus[1] or modulus of [3] elements.
count += modulus[1] / 2;
count += modulus[3] / 2;
// increment count by half of modulus[2]
count += modulus[2] / 2;
return count;
}
}
// Driver Code
public static void Main(String[] args)
{
// size of array
int n = 7;
// input array
int []arr = { 1, 2, 3, 1, 2, 3, 8 };
int count = getSteps(arr, n);
Console.Write("{0}", count);
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP program for the above approach
function getSteps($arr, $n)
{
// Count to keep track of the number
// of steps done.
$count = 0;
// Modulus array to store all elements mod 4
$modulus = array_fill(0, 4, 0);
// sum to check if given task is possible
$sum = 0;
// Loop to store all elements
// mod 4 and calculate sum;
for ($i = 0; $i < $n; $i++)
{
$mod = $arr[$i] % 4;
$sum += $mod;
$modulus[$mod]++;
}
// If sum is not divisible by 4, not possible
if ($sum % 4 != 0)
{
return -1;
}
else
{
// Find minimum of modulus[1] and modulus[3]
// and increment the count by the minimum
if ($modulus[1] > $modulus[3])
{
$count += $modulus[3];
}
else
{
$count += $modulus[1];
}
// Update the values in modulus array.
$modulus[1] -= $count;
$modulus[3] -= $count;
// Use modulus[2] to pair remaining elements.
$modulus[2] += (int)($modulus[1] / 2);
$modulus[2] += (int)($modulus[3] / 2);
// increment count to half of remaining
// modulus[1] or modulus of [3] elements.
$count += (int)($modulus[1] / 2);
$count += (int)($modulus[3] / 2);
// increment count by half of modulus[2]
$count += (int)($modulus[2] / 2);
return $count;
}
}
// Driver Code
// size of array
$n = 7;
// input array
$arr = array( 1, 2, 3, 1, 2, 3, 8 );
$count = getSteps($arr, $n);
print($count);
// This code contributed by mits
?>
Javascript
<script>
function getSteps(arr, n)
{
// Count to keep track of the
// number of steps done.
let count = 0;
// Modulus array to store all elements mod 4
let modulus = new Array(4);
modulus.fill(0);
// sum to check if given task is possible
let sum = 0;
// Loop to store all elements mod 4
// and calculate sum;
let i;
for (i = 0; i < n; i++)
{
let mod = arr[i] % 4;
sum += mod;
modulus[mod]++;
}
// If sum is not divisible by 4,
// not possible
if (sum % 4 != 0)
{
return -1;
}
else
{
// Find minimum of modulus[1] and modulus[3]
// and increment the count by the minimum
if (modulus[1] > modulus[3])
{
count += modulus[3];
}
else
{
count += modulus[1];
}
// Update the values in modulus array.
modulus[1] -= count;
modulus[3] -= count;
// Use modulus[2] to pair remaining elements.
modulus[2] += parseInt(modulus[1] / 2, 10);
modulus[2] += parseInt(modulus[3] / 2, 10);
// increment count to half of remaining
// modulus[1] or modulus of [3] elements.
count += parseInt(modulus[1] / 2, 10);
count += parseInt(modulus[3] / 2, 10);
// increment count by half of modulus[2]
count += parseInt(modulus[2] / 2, 10);
return count;
}
}
// size of array
let n = 7;
// input array
let arr = [ 1, 2, 3, 1, 2, 3, 8 ];
let count = getSteps(arr, n);
document.write(count);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
3
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AbhijeetSridhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA