Hackerrank - Lucky number 8 - week of code 28

LuckyNumber8.cs

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

namespace LuckyNumberEight
{
    class Program
    {
        /*
         * This class is designed to help recusion function - 
         * Go to a small subproblem, one is to skip last insignificant digit or just reserve the
         * digit. Two options only.
         * 
         */
        internal class Last3Digits{
            public bool[] reserved = new bool[3];
            public int[] digits = new int[3];

            public Last3Digits(bool[] input, int[] values)
            {               
                for(int i = 0; i < 3; i++)
                {
                    reserved[i] = input[i];
                    digits[i]   = values[i]; 
                }
            }           

            public static Last3Digits ReserveLastDigit(Last3Digits current, char lastDigit)
            {
                Last3Digits last3Digits = new Last3Digits(current.reserved, current.digits);
                last3Digits.reserved[2] = true;
                last3Digits.digits[2] = Convert.ToInt16(lastDigit);

                return last3Digits;
            }

            public static Last3Digits ReserveLast2Digits(Last3Digits current, string last2Digits)
            {
                Last3Digits last3Digits = new Last3Digits(current.reserved, current.digits);

                last3Digits.reserved[1] = true;
                last3Digits.digits[1] = Convert.ToInt16(last2Digits[0]);

                last3Digits.reserved[2] = true;
                last3Digits.digits[2] = Convert.ToInt16(last2Digits[1]);

                return last3Digits;
            }

            /*
             * update one digit a time
             * 
             */
            public static Last3Digits ReserveLast3Digits(Last3Digits current, string last3DigitsStr)
            {
                Last3Digits last3Digits = new Last3Digits(current.reserved, current.digits);

                last3Digits.reserved[0] = true;
                last3Digits.digits[0] = Convert.ToInt16(last3DigitsStr[0]);

                return last3Digits;
            }                       
        }

        internal class Reserved
        {
            public bool noReserve; 
            public bool lastDigitIsReserverd;
            public bool last2DigitsAreReserverd; 
            public bool last3DigitsAreReserved;

            public Reserved(bool[] reserved)
            {
                noReserve = !reserved[0] && !reserved[1] && !reserved[2];
                lastDigitIsReserverd    = reserved[2]; 
                last2DigitsAreReserverd = reserved[1] && reserved[2]; 
                last3DigitsAreReserved  = reserved[0] && reserved[1] && reserved[2]; 
            }
        }

        /*
         * The design is to work on last 3 least significant digits, and then based on 1000 is 
         * divisbled by 8, no need to discuss in detail. 
         * Just conunt the rest bits in power of 2 options, either in or out 2 options. 
         * 
         * Help to prune the algorithm, some digit can be eliminated quickly. 
         */
        internal class NumberDivisbleBy8
        {
            public HashSet<int> lastDigits  = new HashSet<int>();
            public HashSet<int> last2Digits = new HashSet<int>();
            public HashSet<int> last3Digits = new HashSet<int>();                       

            public NumberDivisbleBy8()
            {
                for (int i = 0; i <= 125; i++)
                {
                    int value  = 8 * i;
                    int by10   = value % 10;
                    int by100  = value % 100;
                    int by1000 = value % 1000;
                    
                    lastDigits.Add(by10);                                                         
                    last2Digits.Add(by100);                                        
                    last3Digits.Add(by1000);                    
                }
            }
        }

        
        internal class StringHelper
        {
            /*
             * input: 001 output: 1 
             * 
             */
            public static string RemoveLeadingZero(string number)
            {
                StringBuilder newString = new StringBuilder();

                if (number.IndexOf('0') != 0)
                    return number;

                bool skipZero = true;
                foreach (char c in number)
                {
                    if (skipZero && c == '0')
                        continue;

                    if (skipZero)
                        skipZero = false;

                    newString.Append(c);
                }

                string result = newString.ToString();
                if (result.Length == 0)
                    return "0";

                return newString.ToString();
            }

            public static int ConvertToInt(string s)
            {
                return Convert.ToInt16(StringHelper.RemoveLeadingZero(s));
            }

            public static bool CheckNumberDivisibleBy8(string s)
            {
                return Convert.ToInt16(StringHelper.RemoveLeadingZero(s)) % 8 == 0;
            }       
        }

        internal class MathHelper
        {
            public static long NUMBER = (long)1000 * 1000 * 1000 + 7;

            public static int GetPowerValue()
            {
                int index = 28;
                while (Math.Pow(2, index) < NUMBER)
                {
                    index++; 
                }

                return index; 
            }
        }

        private static NumberDivisbleBy8 numbersToLookup = new NumberDivisbleBy8();       

        private static IList<string> divisibleString = new List<string>();
        private static IDictionary<string, long> memo = new Dictionary<string, long>();

        private static IList<string> DebugResultLessThan100 = new List<string>(); 

        static void Main(string[] args)
        {                                 
            ProcessInput();

            //RunSampleTestcase();             
            //RunSampleTestcase_1000(); 
            //RunSampleTestcase_12888();
        }

        /*
         * 3
         * 968
         * - subsequences are 8, 96, 968
         */
        public static void RunSampleTestcase_968()
        {
            bool[] reserved = new bool[3] { false, false, false };
            int[] digits    = new int[3];
            long result     = CalculateSumOfSubsequencesDivisibleBy8(3, "968", reserved, digits);
        }

        /*
         * 4
         * 1000
         * Subsequences: 0, 0, 0, 00, 00, 00, 000, 1000
         * 
         * So, the answer should be 8
         * Runing result: score 18 out of 25 if the test case passes. score from 6 to 18. 
         * But there are still 2 iusses - timeout, wrong answer. 
         */
        public static void RunSampleTestcase_1000()
        {
            bool[] reserved = new bool[] { false, false, false, false };
            int[] digits = new int[4];
            long result = CalculateSumOfSubsequencesDivisibleBy8(reserved.Length, "1000", reserved, digits);
            Debug.Assert(result == 8);
        }

        /*
         * 5 
         * 12888
         * - subsequences are 
         * 8, 8, 8, 
         * 88,88, 
         * 288, 288, 288, 
         * 888, 
         * 1288, 1288, 1288,
         * 1888,
         * 2888,
         * 12888
         * 
         * The result is 19
         */
        public static void RunSampleTestcase_12888()
        {
            bool[] reserved = new bool[] { false, false, false, false, false };
            int[] digits = new int[5];
            long result = CalculateSumOfSubsequencesDivisibleBy8(reserved.Length, "12888", reserved, digits);
        }               

        public static void ProcessInput()
        {
            int n = Convert.ToInt32(Console.ReadLine());
            string number = Console.ReadLine();

            bool[] reserved = new bool[3] { false, false, false };
            int[] digits = new int[3]; 
            Console.WriteLine(CalculateSumOfSubsequencesDivisibleBy8(n, number, reserved, digits));
        }

        /*
         * @number - string with digits >=1 and <= 2 * 100 * 1000
         * Subsequence - 
         * Divisible By 8 
         * Find all the subsequence should be divisible by 8, 
         * special cares are needed: 
         * 888 - subsequences are 8, 8, 8, 88, 88, 88, 888
         * if string s= "888", then first 88 are generated by s[0] and s[1], second 
         * 88 are generated by s[0] and s[2], third 88 are generated by s[1] and s[2]. 
         * 
         * the sum should be moduled by 10^9 + 7
         * since 10^3 is around 1024, 10^9 is around 2^30, 
         * N is 
         * 
         */
        public static long CalculateSumOfSubsequencesDivisibleBy8(
            int    n, 
            string number, 
            bool[] reserved, 
            int[]  digits)
        {
            Reserved reservedDigits = new Reserved(reserved);

            if (reservedDigits.noReserve && memo.ContainsKey(number))
                return memo[number]; 

            Debug.Assert(n == number.Length);
            if (n == 0)
                return 0;

            if (n == 1)
            {                             
                bool result = Convert.ToInt16(number) % 8 == 0 ;
                AddDebugResult(result, number);

                long value = (result) ? 1 : 0;
                AddToMemo(number, value);

                return value;
            }

            if (n == 2)
            {
                long value = 0;
                if (reservedDigits.noReserve)
                {
                    value = CalculateSumOfSubsequencesDivisibleBy8(1, number[0].ToString(), reserved, digits)
                          + CalculateSumOfSubsequencesDivisibleBy8(1, number[1].ToString(), reserved, digits)
                          + ((Convert.ToInt16(number) % 8 == 0) ? 1 : 0);                    

                    AddDebugResult(number[0].ToString());
                    AddDebugResult(number[1].ToString());
                    AddDebugResult(Convert.ToInt16(number) % 8 == 0, number);
                }
                else if (reservedDigits.lastDigitIsReserverd)
                {
                    value = CalculateSumOfSubsequencesDivisibleBy8(1, number[1].ToString(), reserved, digits)
                          + ((Convert.ToInt16(number) % 8 == 0) ? 1 : 0);

                    AddDebugResult(number[1].ToString());
                    AddDebugResult(Convert.ToInt16(number) % 8 == 0, number);
                }
                else if (reservedDigits.last2DigitsAreReserverd)
                {
                    value = ((Convert.ToInt16(number) % 8 == 0) ? 1 : 0);
                    
                    AddDebugResult(Convert.ToInt16(number) % 8 == 0, number);
                }

                AddToMemo(number, value); 

                return value;
            }

            string last3DigitsToLast = number.Substring(n - 3, 3);

            string thirdToLast  = last3DigitsToLast[0].ToString();
            string secondToLast = last3DigitsToLast[1].ToString();
            string firstToLast  = last3DigitsToLast[2].ToString();

            string firstTwoChars = thirdToLast + secondToLast;
            string twoEnds       = thirdToLast + firstToLast;
            string lastTwoChars  = secondToLast + firstToLast;

            if (n == 3)
            {
                long value = 0;

                if (reservedDigits.noReserve)
                {
                    value = CalculateSumOfSubsequencesDivisibleBy8(1, thirdToLast, reserved, digits)
                     + CalculateSumOfSubsequencesDivisibleBy8(1, secondToLast, reserved, digits)
                     + CalculateSumOfSubsequencesDivisibleBy8(1, firstToLast, reserved, digits)
                     + (StringHelper.CheckNumberDivisibleBy8(firstTwoChars) ? 1 : 0)
                     + (StringHelper.CheckNumberDivisibleBy8(twoEnds) ? 1 : 0)
                     + (StringHelper.CheckNumberDivisibleBy8(lastTwoChars) ? 1 : 0)
                     + (StringHelper.CheckNumberDivisibleBy8(number) ? 1 : 0);
                }
                else if (reservedDigits.last3DigitsAreReserved)
                {
                    value = (StringHelper.CheckNumberDivisibleBy8(number) ? 1 : 0);
                }
                else if (reservedDigits.last2DigitsAreReserverd)
                {
                    value = (StringHelper.CheckNumberDivisibleBy8(lastTwoChars) ? 1 : 0)
                     + (StringHelper.CheckNumberDivisibleBy8(number) ? 1 : 0);
                }
                else if (reservedDigits.lastDigitIsReserverd)
                {
                    value = CalculateSumOfSubsequencesDivisibleBy8(1, firstToLast, reserved, digits)
                     + (StringHelper.CheckNumberDivisibleBy8(twoEnds) ? 1 : 0)
                     + (StringHelper.CheckNumberDivisibleBy8(lastTwoChars) ? 1 : 0)
                     + (StringHelper.CheckNumberDivisibleBy8(number) ? 1 : 0);
                }

                AddToMemo(number, value); 

                return value;
            }

            string substring = number.Substring(0, n - 3);
            long moduleNo = 1000000000 + 7;

            long sum = 0;

            Last3Digits current = new Last3Digits(reserved, digits);
            

            /* go over cases in the following orders:                                   
               last 3 digits are reserved
               last two digits are reserved
               last digit is reserved
               no digits reserved
             
               At most 3 digits are reserved. Since 1000 is divisble by 8, no need to go further.
             */

            // no reserved 
            if (reservedDigits.last3DigitsAreReserved)
            {
                // last 3 digits reserved are divisible by 8, and 1000 is divisible by 8 
                // For example, 
                // 123xyz - xyz may be 160, so first 3 digits, how many subsequence, 2^3                
                // 2^30 is around 10^9 
                //long sum = 0; 

                int maximumNo = MathHelper.GetPowerValue(); 

                sum = 1;
                int index = n - 3;  // do not count last 3 digits...                
                if( index > 0)
                {
                    int value = Math.Min(maximumNo, index); 
                    sum = (sum * (long)Math.Pow(2, value) % moduleNo) % moduleNo;

                    index -= value; 
                }

                AddDebugResult("Add value " + sum.ToString());                 

                return sum; 
            }
            else if (reservedDigits.last2DigitsAreReserverd)
            {
                // skip 3rd to last digit                
                string shortOne = number.Substring(0, n - 3) + number.Substring(n-2,2);
                sum = (sum + CalculateSumOfSubsequencesDivisibleBy8(n - 1, shortOne, reserved, digits)) % moduleNo; 

                // if 3rd to last digit can be reserved, the reserve the digit
                string last3DigitsStr = number.Substring(n - 3, 3);
                if (StringHelper.CheckNumberDivisibleBy8(last3DigitsStr))
                {
                    Last3Digits last3Digits = Last3Digits.ReserveLast3Digits(current, last3DigitsStr);
                    sum = (sum + CalculateSumOfSubsequencesDivisibleBy8(n, number, last3Digits.reserved, last3Digits.digits)) % moduleNo;
                }

                return sum; 
            }
            else if (reservedDigits.lastDigitIsReserverd)
            {
                // skip 2nd to last digit
                string shortOne = number.Substring(0, n - 2) + number[n-1];
                sum = (sum + CalculateSumOfSubsequencesDivisibleBy8(n - 1, shortOne, reserved, digits)) % moduleNo;               

                // if 2nd to last digit can be reserved, then reserve the digit
                string last2Digits = number.Substring(n - 2, 2);
                if (numbersToLookup.last2Digits.Contains(StringHelper.ConvertToInt(last2Digits)))
                {
                    Last3Digits last3Digits = Last3Digits.ReserveLast2Digits(current, last2Digits);
                    sum = (sum + CalculateSumOfSubsequencesDivisibleBy8(n, number, last3Digits.reserved, last3Digits.digits)) % moduleNo;
                }

                return sum; 
            }     
            else    // if (NoReserved(reserved))
            {
                // last digit - just skip it
                string shortOne = number.Substring(0, n - 1);
                long value  = CalculateSumOfSubsequencesDivisibleBy8(n - 1, shortOne, reserved, digits) % moduleNo;              

                sum = sum + value; 
                // if last digit is in the set, then, try to reserve the digit
                if (numbersToLookup.lastDigits.Contains(Convert.ToInt16(firstToLast)))
                {
                    // reserve last digit
                    Last3Digits last3Digits = Last3Digits.ReserveLastDigit(current, firstToLast[0]); 
                    sum = (sum + CalculateSumOfSubsequencesDivisibleBy8(n, number, last3Digits.reserved, last3Digits.digits )) % moduleNo;
                }               

                return sum;
            }                  
        }

        private static void AddToMemo(string number, long result)
        {
            if (!memo.ContainsKey(number))
            {
                memo.Add(number, result); 
            }
        }

        private static void AddDebugResult(bool result, string number)
        {
            if (result && DebugResultLessThan100.Count < 100)
            {
                DebugResultLessThan100.Add(number); 
            }
        }

        private static void AddDebugResult( string number)
        {
            if ( DebugResultLessThan100.Count < 100)
            {
                DebugResultLessThan100.Add(number);
            }
        }             
    }
}