class Solution {
    public int[] prisonAfterNDays(int[] cells, int N) {

        int index = 0;
        HashMap<String,Integer> map = new HashMap<>();
        String currentVariation = "";

        while (true)
        {
            if (index == N) return cells;
            int prev = cells[0];
            currentVariation = "" + 0;
            for (int j = 1; j < cells.length - 1; j++)
            {
                if (prev + cells[j+1] != 1)
                {
                    prev = cells[j];
                    cells[j] = 1;
                }
                else
                {
                    prev = cells[j];
                    cells[j] = 0;
                }
                currentVariation += cells[j];
            }

            cells[0] = 0;
            cells[cells.length-1] = 0;
            currentVariation += 0;

            if (!map.containsKey(currentVariation)) map.put(currentVariation,index+1);
            else break;

            index++;
        }

        Integer variationToGet = N % index == 0 ? index : N % index;
        String ret = "";

        for(Map.Entry entry: map.entrySet()){
            if(variationToGet.equals(entry.getValue())){
                ret = entry.getKey().toString();
                break;
            }
        }

        for (int i = 1; i < ret.length() - 1; i++)
        {
            cells[i] = Character.getNumericValue(ret.charAt(i));
        }

        return cells;
    }
}