Wednesday, September 7, 2016

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);`
`}`