Arrays: Cell state after K days

Problem Statement:

You are given a binary array of size “n” where “n > 3”.

Where in “1” is active, “0” means inactive.

You are given a number “k” and the task is to find the count of active and inactive cells after “k” days.

Rule is:

1. After every day, status of the ith cell becomes active if left and right cells are not same

2. Inactive if left and right cells are same

Note:

Since there are no cells before the leftmost and after rightmost cells, the value of the cells before leftmost and after rightmost can be considered as zero.

Example:
———————-

Input  : array[] = {1, 0, 1, 1}, k = 2
Output : Active cells = 3, Inactive cells = 1

After 1 day: array[] = {0, 0, 1, 1}
After 2 day: array[] = {0, 1, 1, 1}

Solution Explanation:

1. Copy the original array into a temp array and make changes in temp array according to the rules.

2. As per the rules, if the immediate left and right of i’th cell either inactive or active, the next day, i becomes inactive.

i.e (arr[i-1] == 0 and arr[i+1] == 0) or (arr[i-1] == 1 and arr[i+1] == 1) then arr[i] = 0.

For this we will use XOR of arr[i-1] and arr[i+1]

3. For 0th index temp[0] = 0 ^ arr[1] and for (n-1)th index cell temp[n-1] = 0^arr[n-2].

4. So, for the index 1 to n-2, we will follow arr[i-1] ^ arr[i+1].

5. Repeat the process till K days are completed.

Time complexity: O(N*K) where N is size of an array and K is number of days.
Auxiliary space: O(N) for temp array

Code Solution

#include<iostream>
using namespace std;

void solution(bool cells[], int n, int k)
{
	bool temp[n];
	
	//copy the original array into temp array
	for (int i=0; i<n ; i++)
		temp[i] = cells[i];

	// Iterate for k days
	while (k--)
	{
		// update the values for 0th and n-1th index
		temp[0] = 0^cells[1];
		temp[n-1] = 0^cells[n-2];

        //check the values of remaining cells.
		for (int i=1; i<=n-2; i++)
			temp[i] = cells[i-1] ^ cells[i+1];

		// now, copy the temp array into original array
		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);
}

int main()
{
	bool cells[] = {0, 1, 0, 1, 0, 1, 0, 1};
	int k = 3;
	int n = sizeof(cells)/sizeof(cells[0]);
	solution(cells, n, k);
	return 0;
}

Output

Active Cells = 2, Inactive Cells = 6