Dada una array binaria de tamaño n donde n > 3 . Un valor verdadero (o 1) en la array significa activo y falso (o 0) significa inactivo. Dado un número k, la tarea es encontrar el recuento de celdas activas e inactivas después de k días. Después de cada día, el estado de la i-ésima celda se vuelve activo si las celdas izquierda y derecha no son iguales e inactivo si las celdas izquierda y derecha son iguales (ambas 0 o ambas 1).
Dado que no hay celdas antes de las celdas más a la izquierda y después de las celdas más a la derecha, las celdas de valor antes de las celdas más a la izquierda y después de las celdas más a la derecha siempre se consideran 0 (o inactivas).
Ejemplos:
Input : cells[] = {1, 0, 1, 1}, k = 2
Output : Active cells = 3, Inactive cells = 1
After 1 day, cells[] = {0, 0, 1, 1}
After 2 days, cells[] = {0, 1, 1, 1}
Input : cells[] = {0, 1, 0, 1, 0, 1, 0, 1}, k = 3
Output: Active Cells = 2 , Inactive Cells = 6
Explanation :
After 1 day, cells[] = {1, 0, 0, 0, 0, 0, 0, 0}
After 2 days, cells[] = {0, 1, 0, 0, 0, 0, 0, 0}
After 3 days, cells[] = {1, 0, 1, 0, 0, 0, 0, 0}
Input : cells[] = {0, 1, 1, 1, 0, 1, 1, 0}, k = 4
Output: Active Cells = 3 , Inactive Cells = 5
Lo único importante es asegurarse de mantener una copia de la array dada porque necesitamos que los valores anteriores se actualicen para el día siguiente. A continuación se detallan los pasos.
- Primero copiamos la array de celdas [] en la array temp [] y hacemos cambios en la array temp [] de acuerdo con la condición dada.
- En la condición, se da que si la celda izquierda y derecha inmediata de la i-ésima celda está inactiva o activa al día siguiente, i se vuelve inactiva, es decir; (celdas[i-1] == 0 y celdas[i+1] == 0) o (celdas[i-1] == 1 y celdas[i+1] == 1) luego celdas[i] = 0 , estas condiciones se pueden aplicar usando XOR de celdas [i-1] y celdas [i+1].
- Para 0’th index cell temp[0] = 0^cells[1] y para (n-1)’th index cell temp[n-1] = 0^cells[n-2].
- Ahora, para el índice 1 a n-2, realice la siguiente operación temp[i] = celdas[i-1] ^ celdas[i+1]
- Repita el proceso hasta completar k días.
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program to count active and inactive cells after k
// days
#include<bits/stdc++.h>
using namespace std;
// cells[] - store current status of cells
// n - Number of cells
// temp[] - to perform intermediate operations
// k - number of days
// active - count of active cells after k days
// inactive - count of active cells after k days
void activeAndInactive(bool cells[], int n, int k)
{
// copy cells[] array into temp [] array
bool temp[n];
for (int i=0; i<n ; i++)
temp[i] = cells[i];
// Iterate for k days
while (k--)
{
// Finding next values for corner cells
temp[0] = 0^cells[1];
temp[n-1] = 0^cells[n-2];
// Compute values of intermediate cells
// If both cells active or inactive, then temp[i]=0
// else temp[i] = 1.
for (int i=1; i<=n-2; i++)
temp[i] = cells[i-1] ^ cells[i+1];
// Copy temp[] to cells[] for next iteration
for (int i=0; i<n; i++)
cells[i] = temp[i];
}
// count active and inactive cells
int active = 0, inactive = 0;
for (int i=0; i<n; i++)
(cells[i] == 1)? active++ : inactive++;
printf("Active Cells = %d, Inactive Cells = %d",
active, inactive);
}
// Driver program to check the test case
int main()
{
bool cells[] = {0, 1, 0, 1, 0, 1, 0, 1};
int k = 3;
int n = sizeof(cells)/sizeof(cells[0]);
activeAndInactive(cells, n, k);
return 0;
}
Java
// Java program to count active and
// inactive cells after k days
class GFG {
// cells[] - store current status
// of cells n - Number of cells
// temp[] - to perform intermediate operations
// k - number of days
// active - count of active cells after k days
// inactive - count of active cells after k days
static void activeAndInactive(boolean cells[],
int n, int k)
{
// copy cells[] array into temp [] array
boolean temp[] = new boolean[n];
for (int i = 0; i < n; i++)
temp[i] = cells[i];
// Iterate for k days
while (k-- > 0) {
// Finding next values for corner cells
temp[0] = false ^ cells[1];
temp[n - 1] = false ^ cells[n - 2];
// Compute values of intermediate cells
// If both cells active or inactive, then
// temp[i]=0 else temp[i] = 1.
for (int i = 1; i <= n - 2; i++)
temp[i] = cells[i - 1] ^ cells[i + 1];
// Copy temp[] to cells[] for next iteration
for (int i = 0; i < n; i++)
cells[i] = temp[i];
}
// count active and inactive cells
int active = 0, inactive = 0;
for (int i = 0; i < n; i++)
if (cells[i] == true)
active++;
else
inactive++;
System.out.print("Active Cells = " + active + ", " +
"Inactive Cells = " + inactive);
}
// Driver code
public static void main(String[] args)
{
boolean cells[] = {false, true, false, true,
false, true, false, true};
int k = 3;
int n = cells.length;
activeAndInactive(cells, n, k);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to count
# active and inactive cells after k
# days
# cells[] - store current
# status of cells
# n - Number of cells
# temp[] - to perform
# intermediate operations
# k - number of days
# active - count of active
# cells after k days
# inactive - count of active
# cells after k days
def activeAndInactive(cells,n,k):
# copy cells[] array into temp [] array
temp=[]
for i in range(n+1):
temp.append(False)
for i in range(n):
temp[i] = cells[i]
# Iterate for k days
while (k >0):
# Finding next values for corner cells
temp[0] = False^cells[1]
temp[n-1] = False^cells[n-2]
# Compute values of intermediate cells
# If both cells active or
# inactive, then temp[i]=0
# else temp[i] = 1.
for i in range(1,n-2+1):
temp[i] = cells[i-1] ^ cells[i+1]
# Copy temp[] to cells[]
# for next iteration
for i in range(n):
cells[i] = temp[i]
k-=1
# count active and inactive cells
active = 0
inactive = 0;
for i in range(n):
if(cells[i] == True):
active+=1
else:
inactive+=1
print("Active Cells =",active," , "
, "Inactive Cells =",
inactive)
# Driver code
cells = [False, True, False, True,
False, True, False, True]
k = 3
n =len(cells)
activeAndInactive(cells, n, k)
# This code is contributed
# by Anant Agarwal.
C#
// C# program to count active and
// inactive cells after k days
using System;
class GFG {
// cells[] - store current status
// of cells n - Number of cells
// temp[] - to perform intermediate
// operations k - number of days
// active - count of active cells
// after k days inactive - count
// of active cells after k days
static void activeAndInactive(bool []cells,
int n, int k)
{
// copy cells[] array into
// temp [] array
bool []temp = new bool[n];
for (int i = 0; i < n; i++)
temp[i] = cells[i];
// Iterate for k days
while (k-- > 0) {
// Finding next values
// for corner cells
temp[0] = false ^ cells[1];
temp[n - 1] = false ^ cells[n - 2];
// Compute values of intermediate cells
// If both cells active or inactive, then
// temp[i]=0 else temp[i] = 1.
for (int i = 1; i <= n - 2; i++)
temp[i] = cells[i - 1] ^ cells[i + 1];
// Copy temp[] to cells[]
// for next iteration
for (int i = 0; i < n; i++)
cells[i] = temp[i];
}
// count active and inactive cells
int active = 0, inactive = 0;
for (int i = 0; i < n; i++)
if (cells[i] == true)
active++;
else
inactive++;
Console.Write("Active Cells = " + active + ", " +
"Inactive Cells = " + inactive);
}
// Driver code
public static void Main()
{
bool []cells = {false, true, false, true,
false, true, false, true};
int k = 3;
int n = cells.Length;
activeAndInactive(cells, n, k);
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to count active
// and inactive cells after k
// days
// cells[] - store current status
// of cells n - Number of cells
// temp[] - to perform intermediate
// operations k - number of days
// active - count of active cells
// after k days inactive - count of
// active cells after k days
function activeAndInactive($cells, $n, $k)
{
// copy cells[] array into
// temp [] array
$temp = array();
for ($i = 0; $i < $n ; $i++)
$temp[$i] = $cells[$i];
// Iterate for k days
while ($k--)
{
// Finding next values
// for corner cells
$temp[0] = 0 ^ $cells[1];
$temp[$n - 1] = 0 ^ $cells[$n - 2];
// Compute values of
// intermediate cells
// If both cells active
// or inactive, then temp[i]=0
// else temp[i] = 1.
for ($i = 1; $i <= $n - 2; $i++)
$temp[$i] = $cells[$i - 1] ^
$cells[$i + 1];
// Copy temp[] to cells[]
// for next iteration
for ($i = 0; $i < $n; $i++)
$cells[$i] = $temp[$i];
}
// count active and
// inactive cells
$active = 0;$inactive = 0;
for ($i = 0; $i < $n; $i++)
($cells[$i] == 1)? $active++ : $inactive++;
echo "Active Cells = ", $active, " ,Inactive Cells = ",
$inactive;
}
// Driver Code
$cells= array(0, 1, 0, 1, 0, 1, 0, 1);
$k = 3;
$n = count($cells);
activeAndInactive($cells, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript program to count active and
// inactive cells after k days
// cells - store current status
// of cells n - Number of cells
// temp - to perform intermediate operations
// k - number of days
// active - count of active cells after k days
// inactive - count of active cells after k days
function activeAndInactive(cells , n , k)
{
// copy cells array into temp array
var temp = Array(n).fill(false);
for (i = 0; i < n; i++)
temp[i] = cells[i];
// Iterate for k days
while (k-- > 0)
{
// Finding next values for corner cells
temp[0] = false ^ cells[1];
temp[n - 1] = false ^ cells[n - 2];
// Compute values of intermediate cells
// If both cells active or inactive, then
// temp[i]=0 else temp[i] = 1.
for (i = 1; i <= n - 2; i++)
temp[i] = cells[i - 1] ^ cells[i + 1];
// Copy temp to cells for next iteration
for (i = 0; i < n; i++)
cells[i] = temp[i];
}
// count active and inactive cells
var active = 0, inactive = 0;
for (i = 0; i < n; i++)
if (cells[i] == true)
active++;
else
inactive++;
document.write("Active Cells = " + active + ", " + "Inactive Cells = " + inactive);
}
// Driver code
var cells = [ false, true, false, true, false, true, false, true ];
var k = 3;
var n = cells.length;
activeAndInactive(cells, n, k);
// This code is contributed by Rajput-Ji
</script>
Producción
Active Cells = 2, Inactive Cells = 6
Complejidad de tiempo: O(N*K) donde N es el tamaño de una array y K es el número de días.
Espacio auxiliar: O(N)
Este artículo es una contribución de Shashank Mishra (Gullu) . Este artículo está revisado por el equipo geeksforgeeks. Si tiene un mejor enfoque para este problema, por favor comparta.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA