-
Notifications
You must be signed in to change notification settings - Fork 2
/
PrisonCellsAfterNDays.java
97 lines (88 loc) · 2.79 KB
/
PrisonCellsAfterNDays.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package Leetcode;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* @author kalpak
*
* 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.
*
* You are given an integer array cells where cells[i] == 1 if the ith cell is occupied
* and cells[i] == 0 if the ith cell is vacant, and you are given an integer n.
*
* Return the state of the prison after n days (i.e., 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]
*
*
* Constraints:
*
* cells.length == 8
* cells[i] is either 0 or 1.
* 1 <= n <= 10^9
*
*/
public class PrisonCellsAfterNDays {
public static int[] prisonAfterNDays(int[] cells, int n) {
Set<String> set = new HashSet<>();
int sizeOfCycle = 0;
boolean flag = false;
for(int i = 0; i < n; i++) {
int[] nextState = new int[8];
for(int j = 1; j < 7; j++) {
nextState[j] = (cells[j - 1] == cells[j + 1] ? 1 : 0);
}
String s = Arrays.toString(nextState);
if(!set.contains(s)) {
set.add(s);
sizeOfCycle++;
} else {
// cycle found
flag = true;
break;
}
cells = nextState; // update the cell for the next day
}
if(flag) {
// reduce n by the cycle size
n = n % sizeOfCycle;
for(int i = 0; i < n; i++) {
int[] nextState = new int[8];
for(int j = 1; j < 7; j++) {
nextState[j] = (cells[j - 1] == cells[j + 1] ? 1 : 0);
}
cells = nextState; // update the cell for the next day
}
}
return cells;
}
public static void main(String[] args) {
int[] cells = new int[]{0,1,0,1,1,0,0,1};
System.out.println(Arrays.toString(prisonAfterNDays(cells, 7)));
}
}