Dada una array de N elementos y cada elemento es 1 o 0. Debe hacer que todos los elementos de la array sean iguales a 0 realizando las siguientes operaciones:
- Si un elemento es 1, puede cambiar su valor igual a 0 entonces,
- si el siguiente elemento consecutivo es 1, se convertirá automáticamente en 0.
- si el siguiente elemento consecutivo ya es 0, no pasará nada.
Ahora, la tarea es encontrar el número mínimo de operaciones requeridas para hacer que todos los elementos sean iguales a 0.
Ejemplos :
Input : arr[] = {1, 1, 0, 0, 1, 1, 1, 0, 0, 1}
Output : Minimum changes: 3
Input : arr[] = {1, 1, 1, 1}
Output : Minimum changes: 1
Enfoque 1:
Para encontrar la cantidad mínima de cambios requeridos, itere la array de izquierda a derecha y verifique si el elemento actual es 1 o no. Si el elemento actual es 1, cámbielo a 0 e incremente el conteo en 1 y busque el 0 para la siguiente operación, ya que todos los 1 consecutivos se convertirán automáticamente en 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find minimum number of
// operations required to make all
// array elements zero
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum number of
// operations required to make all
// array elements zero
int minimumChanges(int arr[], int n)
{
int i;
// It will maintain total changes required
int changes = 0;
for (i = 0; i < n; i++)
{
// Check for the first 1
if (arr[i] == 1)
{
int j;
// Check for number of
// consecutive 1's
for(j = i+1; j<n; j++)
{
if(arr[j]==0)
break;
}
// Increment i to the position of
// last consecutive 1
i = j-1;
changes++;
}
}
return changes;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 0, 0, 0, 1, 0, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum operations: " << minimumChanges(arr, n);
return 0;
}
Java
// Java program to find minimum
// number of operations required
// to make all array elements zero
class GFG
{
// Function to find minimum number
// of operations required to make
// all array elements zero
static int minimumChanges(int arr[],
int n)
{
int i;
// It will maintain total
// changes required
int changes = 0;
for (i = 0; i < n; i++)
{
// Check for the first 1
if (arr[i] == 1)
{
int j;
// Check for number of
// consecutive 1's
for(j = i + 1; j < n; j++)
{
if(arr[j] == 0)
break;
}
// Increment i to the position
// of last consecutive 1
i = j - 1;
changes++;
}
}
return changes;
}
// Driver code
public static void main (String args[])
{
int arr[] = { 1, 1, 0, 0, 0,
1, 0, 1, 1 };
int n = arr.length ;
System.out.println("Minimum operations: " +
minimumChanges(arr, n));
}
}
// This code is contributed by ANKITRAI1
Python 3
# Python 3 program to find
# minimum number of operations
# required to make all array
# elements zero
# Function to find minimum number
# of operations required to make
# all array elements zero
def minimumChanges(arr, n) :
# It will maintain total
# changes required
changes = 0
i = 0
while i < n :
# Check for the first 1
if arr[i] == 1 :
j = i + 1
# Check for number of
# consecutive 1's
while j < n:
if arr[j] == 0 :
break
j += 1
# Increment i to the position
# of last consecutive 1
i = j - 1
changes += 1
i += 1
return changes
# Driver code
if __name__ == "__main__" :
arr = [ 1, 1, 0, 0, 0, 1, 0, 1, 1]
n = len(arr)
print("Minimum operations:",
minimumChanges(arr, n))
# This code is contributed by ANKITRAI1
C#
// C# program to find minimum
// number of operations required
// to make all array elements zero
class GFG
{
// Function to find minimum number
// of operations required to make
// all array elements zero
static int minimumChanges(int[] arr,
int n)
{
int i;
// It will maintain total
// changes required
int changes = 0;
for (i = 0; i < n; i++)
{
// Check for the first 1
if (arr[i] == 1)
{
int j;
// Check for number of
// consecutive 1's
for(j = i + 1; j < n; j++)
{
if(arr[j] == 0)
break;
}
// Increment i to the position
// of last consecutive 1
i = j - 1;
changes++;
}
}
return changes;
}
// Driver code
static void Main()
{
int[] arr = new int[]{ 1, 1, 0, 0, 0,
1, 0, 1, 1 };
int n = arr.Length ;
System.Console.WriteLine("Minimum operations: " +
minimumChanges(arr, n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find minimum number
// of operations required to make all
// array elements zero
// Function to find minimum number
// of operations required to make
// all array elements zero
function minimumChanges($arr, $n)
{
$i;
// It will maintain total
// changes required
$changes = 0;
for ($i = 0; $i < $n; $i++)
{
// Check for the first 1
if ($arr[$i] == 1)
{
$j;
// Check for number of
// consecutive 1's
for($j = $i + 1; $j < $n; $j++)
{
if($arr[$j] == 0)
break;
}
// Increment i to the position
// of last consecutive 1
$i = $j - 1;
$changes++;
}
}
return $changes;
}
// Driver code
$arr = array( 1, 1, 0, 0, 0,
1, 0, 1, 1 );
$n = sizeof($arr);
echo "Minimum operations: " .
minimumChanges($arr, $n);
// This code is contributed
// by Akanksha Rai(Abby_akku)
Javascript
<script>
// Javascript program to find minimum number of
// operations required to make all
// array elements zero
// Function to find minimum number of
// operations required to make all
// array elements zero
function minimumChanges(arr, n)
{
var i;
// It will maintain total changes required
var changes = 0;
for (i = 0; i < n; i++)
{
// Check for the first 1
if (arr[i] == 1)
{
var j;
// Check for number of
// consecutive 1's
for(j = i+1; j<n; j++)
{
if(arr[j]==0)
break;
}
// Increment i to the position of
// last consecutive 1
i = j-1;
changes++;
}
}
return changes;
}
// Driver code
var arr = [1, 1, 0, 0, 0, 1, 0, 1, 1 ];
var n = arr.length;
document.write( "Minimum operations: " + minimumChanges(arr, n));
</script>
Producción:
Minimum operations: 3
Complejidad de tiempo: O(N*N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Enfoque 2:
- Como ya sabemos, tenemos que buscar el grupo/clúster consecutivo de ‘1’, ya que después de cambiar el primer ‘1’ del grupo, el resto de los ‘1’ consecutivos se cambiarán automáticamente. Entonces, para encontrar el ‘1’ consecutivo, podemos iterar sobre la array y encontrar el no. de pares consecutivos de ‘1’ y ‘0’, ya que indicará el punto de ruptura para ‘1’ consecutivos.
- Y en el último índice, comprobaremos si el último elemento de la array es ‘1’ o ‘0’, porque, si es ‘1’, entonces es posible que haya un grupo continuo de ‘1’ y por lo tanto nuestro bucle no pudo encontrar el punto de interrupción cuando finalizó la iteración.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find minimum number of
// operations required to make all
// array elements zero
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum number of
// operations required to make all
// array elements zero
int minimumChanges(int arr[], int n)
{
int i;
// It will maintain total changes
// required and return as
// answer
int changes = 0;
// We iterate from 0 to n-1
// We can't iterate from 0 to n as
// the arr[i+1] will be
// out of index
for (i = 0; i < n-1; i++) {
// If we there is a consecutive pair of '1' and
// '0'(in respective order)
if ((arr[i] == 1) && (arr[i + 1] == 0)) {
// We increment our returning variable by 1
changes++;
}
}
// After the loop ends, we check the last element
// whether it is '1'
if (arr[n - 1] == 1) {
changes++;
// If it is '1', we again increment our
// returning variable by 1
}
return changes;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 0, 0, 0, 1, 0, 1, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum operations: "
<< minimumChanges(arr, n);
return 0;
}
// This code is contributed by yashbro
Java
// Java program to find minimum number of
// operations required to make all
// array elements zero
class GFG
{
// Function to find minimum number of
// operations required to make all
// array elements zero
public static int minimumChanges(int arr[], int n)
{
int i;
// It will maintain total changes
// required and return as
// answer
int changes = 0;
// We iterate from 0 to n-1
// We can't iterate from 0 to n as
// the arr[i+1] will be
// out of index
for (i = 0; i < n-1; i++) {
// If we there is a consecutive pair of '1' and
// '0'(in respective order)
if ((arr[i] == 1) && (arr[i + 1] == 0)) {
// We increment our returning variable by 1
changes++;
}
}
// After the loop ends, we check the last element
// whether it is '1'
if (arr[n - 1] == 1) {
changes++;
// If it is '1', we again increment our
// returning variable by 1
}
return changes;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 1, 0, 0, 0, 1, 0, 1, 1 };
int n = arr.length;
System.out.println( "Minimum operations: "+ minimumChanges(arr, n));
}
}
//This code is contributed by sravan kumar
Python3
# Python 3 program to find
# minimum number of operations
# required to make all array
# elements zero
# Function to find minimum number
# of operations required to make
# all array elements zero
def minimumChanges(arr, n):
# It will maintain total
# changes required
changes = 0
# We iterate from 0 to n-1
# We can't iterate from 0 to n as the arr[i+1] will be out of index
for i in range(n - 1):
# If we there is a consecutive pair of '1' and '0'(in respective order)
if arr[i] == 1 and arr[i + 1] == 0:
# We increment our returning variable by 1
changes += 1
# After the loop ends, we check the last element whether it is '1'
if arr[n - 1] == 1:
changes += 1 # If it is '1', we again increment our returning variable by 1
return changes
# Driver code
if __name__ == "__main__":
arr = [1, 1, 0, 0, 0, 1, 0, 1, 1]
n = len(arr)
print("Minimum operations:",
minimumChanges(arr, n))
# This code is contributed by yashbro
C#
// C# program to find minimum number of
// operations required to make all
// array elements zero
using System;
class GFG
{
// Function to find minimum number of
// operations required to make all
// array elements zero
static int minimumChanges(int[] arr, int n)
{
int i;
// It will maintain total changes
// required and return as
// answer
int changes = 0;
// We iterate from 0 to n-1
// We can't iterate from 0 to n as
// the arr[i+1] will be
// out of index
for (i = 0; i < n - 1; i++) {
// If we there is a consecutive pair of '1' and
// '0'(in respective order)
if ((arr[i] == 1) && (arr[i + 1] == 0)) {
// We increment our returning variable by 1
changes++;
}
}
// After the loop ends, we check the last element
// whether it is '1'
if (arr[n - 1] == 1) {
changes++;
// If it is '1', we again increment our
// returning variable by 1
}
return changes;
}
// Driver code
public static int Main()
{
int[] arr = { 1, 1, 0, 0, 0, 1, 0, 1, 1 };
int n = arr.Length;
Console.Write("Minimum operations: "
+ minimumChanges(arr, n));
return 0;
}
}
// This code is contributed by Taranpreet
Javascript
<script>
// Js program to find minimum number of
// operations required to make all
// array elements zero
// Function to find minimum number of
// operations required to make all
// array elements zero
function minimumChanges( arr, n)
{
let i;
// It will maintain total changes
// required and return as
// answer
let changes = 0;
// We iterate from 0 to n-1
// We can't iterate from 0 to n as
// the arr[i+1] will be
// out of index
for (i = 0; i < n-1; i++) {
// If we there is a consecutive pair of '1' and
// '0'(in respective order)
if ((arr[i] == 1) && (arr[i + 1] == 0)) {
// We increment our returning variable by 1
changes++;
}
}
// After the loop ends, we check the last element
// whether it is '1'
if (arr[n - 1] == 1) {
changes++;
// If it is '1', we again increment our
// returning variable by 1
}
return changes;
}
// Driver code
let arr= [1, 1, 0, 0, 0, 1, 0, 1, 1];
let n =arr.length;
document.write("Minimum operations: "
, minimumChanges(arr, n));
</script>
Producción
Minimum operations: 3
Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA