What are the active and inactive cells after k days?

Here we will see an interesting question. Suppose you are given a binary array of size n. Here n > 3. A value of true or 1 indicates active status, and a value of 0 or false indicates inactive status. Another number k is also given. We have to find active or inactive cells after k days. after every time The daytime state of the i-th cell is active if the left and right cells are not the same, and inactive if they are the same. There are no cells before or after the leftmost and rightmost cells. Therefore, the leftmost and rightmost cells are always 0.

Let's look at an example to understand this idea. Suppose an array looks like {0, 1, 0, 1, 0, 1, 0, 1} with the value of k = 3. Let's see how it changes from day to day.

• After 1 days, the array will be {1, 0, 0, 0, 0, 0, 0, 0}
• After 2 days, the array will be {0, 1, 0 , 0, 0, 0, 0, 0}
• After 3 days, the array will be {1, 0, 1, 0, 0, 0, 0, 0}

So 2 active cells and 6 inactive cells

Algorithm

activeCellKdays(arr, n, k)

begin
   make a copy of arr into temp
   for i in range 1 to k, do
      temp[0] := 0 XOR arr[1]
      temp[n-1] := 0 XOR arr[n-2]
      for each cell i from 1 to n-2, do
         temp[i] := arr[i-1] XOR arr[i+1]
      done
      copy temp to arr for next iteration
   done
   count number of 1s as active, and number of 0s as inactive, then return the values.
end

Example

#include <iostream>
using namespace std;
void activeCellKdays(bool arr[], int n, int k) {
   bool temp[n]; //temp is holding the copy of the arr
   for (int i=0; i<n ; i++)
      temp[i] = arr[i];
   for(int i = 0; i<k; i++){
      temp[0] = 0^arr[1]; //set value for left cell
      temp[n-1] = 0^arr[n-2]; //set value for right cell
      for (int i=1; i<=n-2; i++) //for all intermediate cell if left and
         right are not same, put 1
      temp[i] = arr[i-1] ^ arr[i+1];
      for (int i=0; i<n; i++)
         arr[i] = temp[i]; //copy back the temp to arr for the next iteration
   }
   int active = 0, inactive = 0;
   for (int i=0; i<n; i++)
      if (arr[i])
         active++;
      else
         inactive++;
   cout << "Active Cells = "<< active <<", Inactive Cells = " << inactive;
}
main() {
   bool arr[] = {0, 1, 0, 1, 0, 1, 0, 1};
   int k = 3;
   int n = sizeof(arr)/sizeof(arr[0]);
   activeCellKdays(arr, n, k);
}

Output

Active Cells = 2, Inactive Cells = 6

The above is the detailed content of What are the active and inactive cells after k days?. For more information, please follow other related articles on the PHP Chinese website!