Leetcode discuss: 957. Prison Cells After N Days

 Here is the link. 

C# | Quick learner | Bit manipulation warmup | Avoid TLE error

May 10, 2022
I am warmup algorithms to prepare for Google phone screen in 2022. I like to learn and learn quickly.

Introduction
To be a quick learner, I always like to read at least three solutions, and also write C# solutions based one Leetcode discuss post.

Analysis | Intuition | votrubac
Based on the following constraints given in problem statement, we can easily to discuss the scope of problem based on n in range of 2^9, cells.Length = 8.

Constraints:

cells.length == 8
cells[i] is either 0 or 1.
1 <= n <= 10^9

If cells's length is 8, in other words, there are 8 cells, since each cell is either 0 or 1, so the number of all the possible state combinations is 2^8 = 256. This means when N > 256, cells will have the same state as its orignal 256 states. So we expedite the search, avoid time out, reduce calculatuion of next state from n to [loop size] + n % [loop size]. It is challenge task to determine how to take minimum calculation approach in design stage.

For example, given n = 1,000,000, cells is an integer array with size 8, so the total steps to calculate is reduced from n to 256 + n %256, which is at most 512. Reduction from 1,000,000 to 512 is big success to solve this problem without TLE problem.

Using 2^8 vs HashSet | Random state
Since integer array cells's length - denoted as L determines at most 2^L states, it is random process to determine next state, so we can not determine how many states to end the cycle, therefore, we need to store all possible states and use HashSet to determine if it is seen in previous steps.

Of course, it is a good practice to write a solution using bit manipulation. I will try it as well.

Complexity Analysis
Runtime: O(2 ^ n), where n is the number of cells (not days). For 8 cells, we can have 64 different states.

Memory: O(n). We need to remember a single state of all cells for the loop detection. For 8 cells, the complexity is O(1).

The following C# code passes online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _957_prison_state_after_N_days___bit
{
    class Program
    {
        static void Main(string[] args)
        {
            //Input: cells = [0,1,0,1,1,0,0,1], n = 7
            //Output: [0,0,1,1,0,0,0,0]
            var test = new Program();
            var result = PrisonAfterNDays(new int[] { 0, 1, 0, 1, 1, 0, 0, 1 }, 7);
            Debug.Assert(String.Join(",", result).CompareTo("0,0,1,1,0,0,0,0") == 0);
        }

        /// <summary>
        /// study code
        /// https://leetcode.com/problems/prison-cells-after-n-days/discuss/1769581/C-bitwise-op
        /// </summary>
        /// <param name="cells"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int[] PrisonAfterNDays(int[] cells, int n)
        {
            // using 8 bits integer to reprenst each cell in given cells array
            var bits = 0;
            
            for (int i = 0; i < cells.Length; i++)
            {
                // left shift i bits - each cell maps to one bit from left to right
                // | - or operator
                bits |= (cells[i] << i);  
            }

            var map = new Dictionary<int, int>();
            int step = 0;  
            int state = bits;  

            while (!map.ContainsKey(state))  
            {
                map.Add(state, step); 
                step++;

                //01111110 - 8 bits - first bit and last bit will not change 
                //01111110 - 8 bits - integer 126 = 2 ^7 - 1 - 1 = 128 - 1 - 1 = 126
                // if it is easy to understand the above calcuation, then go ahead to read the code

                // shift k left and right to get the next state
                // left shift one bit - 
                var leftShift = (state) << 1;
                var rightShift = (state) >> 1;
                // XOR operator ^, 1 ^ 1 = 0, 1 ^ 0 = 1, 0 ^ 0 = 0

                // Bitwise Complement Operator (~ tilde)
                // the bitwise complement operator is a unary operator 
                // (works on only one operand). It takes one number and 
                // inverts all bits of it. When bitwise operator is applied on bits then, 
                // all the 1’s become 0’s and vice versa. The operator for the bitwise complement is ~ (Tilde).
                // 
                state = ~(leftShift ^ rightShift) & 126;                
            }

            int entryStep = map[state];    
            int L = step - entryStep;

            // avoid TLE error 
            if (n >= entryStep)
            {
                n = (n - entryStep) % L + entryStep;   
            }

            state = bits;
            for (int i = 0; i < n; i++)   // walk n steps from oringal state
            {
                state = ~((state >> 1) ^ (state << 1)) & 126;
            }

            var result = new int[8];
            for (int i = 0; i < cells.Length; i++)  
            {
                // left shift >> i, and determine if it is 0 or 1
                result[i] = (state >> i) & 1;  
            }

            return result;
        }
    }
}