AKTIVE UND INAKTIVE ZELLEN NACH K TAGEN

Gegeben sei ein binäres Array der Größe n, wobei n > 3 . Ein wahrer (oder 1) Wert im Array bedeutet aktiv und falsch (oder 0) bedeutet inaktiv. Bei einer gegebenen Zahl k besteht die Aufgabe darin, die Anzahl der aktiven und inaktiven Zellen nach k Tagen zu ermitteln. Nach jedem Tag wird der Status der i-ten Zelle aktiv, wenn linke und rechte Zelle nicht gleich sind, und inaktiv, wenn linke und rechte Zelle gleich sind (beide 0 oder beide 1).

Da es keine Zellen vor den Zellen ganz links und nach den Zellen ganz rechts gibt, wird der Wert Zellen vor den Zellen ganz links und nach den Zellen ganz rechts immer als 0 (oder inaktiv) betrachtet.

Beispiele:

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

Das einzig Wichtige ist, sicherzustellen, dass wir eine Kopie des angegebenen Arrays behalten, da wir die vorherigen Werte für den nächsten Tag aktualisieren müssen. Nachfolgend finden Sie detaillierte Schritte.

Zuerst kopieren wir das Array „Zellen[] in das Array „Temp[] und nehmen Änderungen im Array „Temp[] entsprechend der gegebenen Bedingung vor.
In der Bedingung ist angegeben, dass, wenn die unmittelbare linke und rechte Zelle der i-ten Zelle entweder inaktiv oder aktiv ist, am nächsten Tag i inaktiv wird, d. h. (Zellen[i-1] == 0 und Zellen[i+1] == 0) oder (Zellen[i-1] == 1 und Zellen[i+1] == 1) dann Zellen[i] == 0 Diese Bedingungen können mithilfe von XOR von Zellen[i-1] und Zellen[i+1] angewendet werden.
Für die 0-te Indexzelle temp[0] = 0^cells[1] und für die (n-1)-te Indexzelle temp[n-1] = 0^cells[n-2].
Führen Sie nun für Index 1 bis n-2 die folgende Operation aus: temp[i] = Zellen[i-1] ^ Zellen[i+1]
Wiederholen Sie den Vorgang, bis k Tage abgeschlossen sind.

Es folgt die Umsetzung der oben genannten Schritte.

C++

// C++ program to count active and inactive cells after k // days #include   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(cellsnk): # 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(1n-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# 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 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>

Ausgabe

Active Cells = 2 Inactive Cells = 6

Zeitkomplexität: O(N*K) Dabei ist N die Größe eines Arrays und K die Anzahl der Tage.
Hilfsraum: O(N)

Dieser Artikel wurde vom Team geeksforgeeks überprüft. Wenn Sie einen besseren Ansatz für dieses Problem haben, teilen Sie ihn bitte mit.

TechCodeview

Aktive und inaktive Zellen nach k Tagen