957

957. Prison Cells After N Days (Medium)

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

• If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
• Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

 

Example 1:

Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: 
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

 

Note:

1. cells.length == 8
2. cells[i] is in {0, 1}
3. 1 <= N <= 10^9

Companies:
Amazon

Related Topics:
Hash Table

Solution 1.

Simulate the process. Once find a cycle, we can get the result from within the cycle.

Since there are at most 256 states, we will get the result at at most 256th day. So the time and space complexity is O(1).

// OJ: https://leetcode.com/problems/prison-cells-after-n-days/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
    char next(char c) {
        char ans = 0;
        for (int i = 1; i < 7; ++i)
            ans |= ((c >> (i - 1) & 1) == (c >> (i + 1) & 1)) << i;
        return ans;
    }
public:
    vector<int> prisonAfterNDays(vector<int>& A, int N) {
        char c = 0;
        for (int i = 0; i < 8; ++i) c |= A[i] << i;
        vector<char> v{c};
        unordered_map<char, int> m{{c, 0}};
        for (int i = 1; i <= N; ++i) {
            c = next(c);
            if (m.count(c)) {
                int d = i - m[c];
                c = v[(N - i) % d + m[c]];
                break;
            }
            v.push_back(c);
            m[c] = i;
        }
        vector<int> ans(8);
        for (int i = 0; i < 8; ++i) ans[i] = (c >> i) & 1;
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/prison-cells-after-n-days/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
    char next(char c) {
        char ans = 0;
        for (int i = 0; i < 8; ++i)
            ans |= (i > 0 && i < 7 && ((c >> (i - 1)) & 1) == ((c >> (i + 1)) & 1)) << i;
        return ans;
    }
public:
    vector<int> prisonAfterNDays(vector<int>& A, int N) {
        char c = 0;
        for (int i = 0; i < 8; ++i) c |= A[i] << i;
        unordered_map<char, int> m{{c, 0}};
        for (int i = 1; i <= N; ++i) {
            c = next(c);
            if (m.count(c)) {
                int d = i - m[c];
                N = (N - i) % d;
                while (N--) c = next(c);
                break;
            }
            m[c] = i;
        }
        vector<int> ans(8);
        for (int i = 0; i < 8; ++i) ans[i] = (c >> i) & 1;
        return ans;
    }
};