Lattice Paths Problem

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Solution:

void Solution()
        {
            //Lattice Path Problem
            //The number of possible path at (i,j) = BinCoff(i+j,j)
            // So for 20x20 matrix it will be
            long x = BinomialCoefficient(40, 20);
        }

        static long BinomialCoefficient(long n, long k)
        {
            // return fact(n) / (fact(k) * fact(n - k));

            long divFactor = k > (n - k) ? k : (n - k);
            long restProd = 1;
            bool flag = true;
            long counter = 1;
            if (divFactor == k)
            {
                for (long i = 0; i < (n - k); i++)
                {
                    restProd = restProd * (k + 1 + i);
                    if (restProd % counter == 0 && flag)
                    {
                        restProd = restProd / counter;
                        //flag = false;
                        counter++;
                    }
                }
                return restProd;// / fact(n - k - counter);
            }
            else
            {
                for (long i = 0; i < k; i++)
                {
                    restProd = restProd * ((n - k) + 1 + i);
                }
                return restProd / fact(k);
            }


        }

        static long fact(long i)
        {
            if (i == 0)
                return 1;
            else
                return i * fact(i - 1);
        }

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1
 3: 1,3
 6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Solution:

void Solution()
        {
            int i = 1;
            int triangleNumber = 0;
            do
            {
                triangleNumber = i * (i + 1) / 2;
                i++;
            }
            while (NoOfDivisors(triangleNumber) <= 500);

            Console.WriteLine(triangleNumber);
        }

        static int NoOfDivisors(int num)
        {
            //Based on the formula, otherwise it will take infinite time
            //Let d(n) be the number of divisors for the natural number, n.
            //We begin by writing the number as a product of prime factors: n = paqbrc...
            //then the number of divisors, d(n) = (a+1)(b+1)(c+1)...

            int counter = 0;
            int totalCount = 1;
            bool flag = false;
            int tempNum = num;
            for (int i = 2; i <= num / 2; i++)
            {
                if (tempNum % i == 0)
                {
                    counter++;
                    tempNum = tempNum / i;
                    i--;
                    flag = true;
                    continue;

                }
                if (flag)
                {
                    totalCount = totalCount * (counter + 1);
                    counter = 0;
                    flag = false;
                }
                if (tempNum == 1)
                    break;
            }

            return totalCount;
        }

Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

Solution :

void Solution()
        {
            int row = 20, col = 20;
            int[,] matrix = new int[,] {{08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08},
                                        {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00},
                                        {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65},
                                        {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91},
                                        {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80},
                                        {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50},
                                        {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70},
                                        {67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21},
                                        {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
                                        {21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95},
                                        {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92},
                                        {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57},
                                        {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58},
                                        {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40},
                                        {04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66},
                                        {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69},
                                        {04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36},
                                        {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16},
                                        {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54},
                                        {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}};

            int prod = 1;
            int maxProd = 1;
            int maxAjd = 4;

            //Scanning RowWise Horizontally
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col - maxAjd + 1; j++)
                {
                    for (int k = 0; k < maxAjd; k++)
                    {
                        prod = prod * matrix[i, j + k];
                    }
                    if (maxProd < prod)
                        maxProd = prod;
                    prod = 1;
                }
            }

            //Scanning ColumnWise Vertically
            for (int i = 0; i < row - maxAjd + 1; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    for (int k = 0; k < maxAjd; k++)
                    {
                        prod = prod * matrix[j, i + k];
                    }
                    if (maxProd < prod)
                        maxProd = prod;
                    prod = 1;
                }
            }

            //Scanning Backward Diagonally
            for (int i = 0; i < row - maxAjd + 1; i++)
            {
                for (int j = 0; j < col - maxAjd + 1; j++)
                {
                    for (int k = 0; k < maxAjd; k++)
                    {
                        prod = prod * matrix[i + k, j + k];
                    }
                    if (maxProd < prod)
                        maxProd = prod;
                    prod = 1;
                }
            }

            //Scanning Forward Diagonally
            for (int i = 0; i < row - maxAjd; i++)
            {
                for (int j = maxAjd - 1; j < col; j++)
                {
                    for (int k = 0; k < maxAjd; k++)
                    {
                        prod = prod * matrix[i + k, j - k];
                    }
                    if (maxProd < prod)
                        maxProd = prod;
                    prod = 1;
                }
            }
        }