Active and Inactive cells after k Days - GeeksforGeeks

Active and Inactive cells after k Days - GeeksforGeeks
Given a binary array of size n where n > 3. A true (or 1) value in the array means active and false (or 0) means inactive. Given a number k, the task is to find count of active and inactive cells after k days. After every day, status of i'th cell becomes inactive if its left and right cells have same value, i.e., either both are 0 or both are 1.
Since there are no cells before leftmost and after rightmost cells, the value cells before leftmost and after rightmost cells is always considered as 0 (or inactive).

The only important thing is to make sure that we maintain a copy of given array because we need previous values to update for next day. Below are detailed steps.

1. First we copy the cells[] array into temp[] array and make changes in temp[] array according to given condition.
2. In the condition, it is given that if immediate left and right cell of i’th cell either inactive or active the next day i becomes inactive i.e; (cells[i-1] == 0 and cells[i+1] == 0) or (cells[i-1] == 1 and cells[i+1] == 1) then cells[i] = 0, these conditions can be applied using XOR of cells[i-1] and cells[i+1].
3. For 0’th index cell temp[0] = 0^cells[1] and for (n-1)’th index cell temp[n-1] = 0^cells[n-2].
4. Now for index 1 to n-2, do the following operation temp[i] = cells[i-1] ^ cells[i+1]
5. Repeat the process till k days are completed.

// 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);

}

Read full article from Active and Inactive cells after k Days - GeeksforGeeks