[Project Euler] Problem 11 in C

Problem: Project Euler Problem 11

This problem was very similar to problem 8 of Project Euler.
I used the same concept proposed in optimizing the code (click this)

Optimizations
Skipping product upon seeing certain "low" digit values.
        Upon inspection of product of randomly chosen 4 numbers, which in my case was (78*78*96*83) resulting in a product of 48477312, we can arrive at a conclusion of ignoring any product containing numbers less than or equal to 49.
        This is because the highest possible product with only 3 digits is 99 * 99 * 99 = 970299. So, simply dividing 48477312/970299 = 49.96... So, even in the best case scenario with the number 49, we cannot exceed the arbitrarily found product. Therefore, we don't even need to compute for products with number less than or equal to 49.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int arr[20][20]=
    {
{ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8},
{49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0},
{81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65},
{52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 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,  3, 45,  2, 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,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21},
{24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
{21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95},
{78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92},
{16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57},
{86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
{19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40},
{ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
{88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
{ 4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18,  8, 46, 29, 32, 40, 62, 76, 36},
{20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74,  4, 36, 16},
{20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54},
{ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48},
    };
    int i, j, k, tmp;
    //1 = left-down, 2 = down, 3 = right-down, 4 = right
    long long int prod1, prod2, prod3, prod4, greatestProd = 0;
    for (i = 0; i < 20; i++){
        for (j = 0; j < 20; j++){
            prod1 = 1, prod2 = 1, prod3 = 1, prod4 = 1;
            for (k = 0; k < 4; k++){
                //left-down
                tmp = arr[i+k][j-k];
                if (tmp >= 50 && j >= 3 && i <= 16)
                    prod1 *= tmp;
                else
                    prod1 = 0;

                //down
                tmp = arr[i+k][j];
                if (tmp >= 50 && i <= 16)
                    prod2 *= tmp;
                else
                    prod2 = 0;

                //right-down
                tmp = arr[i+k][j+k];
                if (tmp >= 50 && i <= 16 && j <= 16)
                    prod3 *= tmp;
                else
                    prod3 = 0;

                //right
                tmp = arr[i][j+k];
                if (tmp >= 50 && j <= 16)
                    prod4 *= tmp;
                else
                    prod4 = 0;
            }

            if (prod1 > greatestProd)
                greatestProd = prod1;
            if (prod2 > greatestProd)
                greatestProd = prod2;
            if (prod3 > greatestProd)
                greatestProd = prod3;
            if (prod4 > greatestProd)
                greatestProd = prod4;
        }
    }
    printf("%lld\n", greatestProd);

    return 0;
}

Best Execution Time: 0.006s
Answer:

70600674

[Project Euler] Problem 9 in C

Problem: Project Euler Problem 9

Algorithm
I decided to approach this problem at more mathematical angle because without doing so, the program will need to iterate through 2 variables instead of 1 variable to arrive at an answer, drastically reducing the runtime.

Optimization
A relationship between two variables has been found on paper through algebra, so, O(n) was achieved instead of O(n^2).

a + b + c = 1000   ...   (1)
a^2 + b^2 = c^2   ...   (2)

Solving a^2 + b^2 = (1000-a-b)^2,
a = 1000 + 500,000 / (b - 1000)   ...   (3)

Iterate through b to solve for a. If a is a natural number, then we have arrived at our solution.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int b = 1, c = 1;
    float a=0;

    for (b = 1; b < 998; b++ ){
        a = 1000.0 + 500000.0/(b-1000.0);
        if ( a == (long)a)    // Check for integer max and min for general use to check if integer
            break;
    }

    c = 1000 - a - b;
    printf("%f\n", a*b*c);
    return 0;
}

Best Execution Time: 0.006s
Answer:

31875000

[Project Euler] Problem 8 in C

Problem: Project Euler Problem 8

Algorithm
This is the brute force way of solving the problem in C.
It is fairly straight forward. Since the question asks us to find the greatest product in five consecutive digits, one loop (w/ iterator i) looped through the entire number, while another loop (w/ iterator j) inside the loop worked with next 4 digits to find the product.
In short, the code just slides 5-digit width along the number to read and find the product.

Possible Optimizations
Since the number is only 1000 digits, I have not made any at optimization in the code posted below. Maybe later, I can revisit it. But here are number of ways of optimizing the code:

1) Using the product from before to calculate the current "slide" of digits.
        Just take a look at first 10 digits of the number given "7316717653"
             7 * 3 * 1 * 6 * 7 = prod1
                   3 * 1 * 6 * 7 * 1 = prod2
                         1 * 6 * 7 * 1 * 7 = prod3
                               6 * 7 * 1 * 7 * 6 = prod4
                                     7 * 1 * 7 * 6 * 5 = prod5
                                           1 * 7 * 6 * 5 * 3 = prod6

        From the example, we can see a pattern that the calculation of the "slide" has their first 4 digit product coincide with last 4 digit product calculation of the previous slide.
        By storing the last 4 digit product for the calculation of the next "slide," we can prevent the computer from recalculating, which reduces our runtime. (Only one loop required to implement this)

2) Skipping product upon seeing certain "low" digit values.
        Upon inspection of product of randomly chosen 5 consecutive digits, which in my case was "66896" resulting in a product of 15552, we can arrive at a conclusion of omitting any "slide" containing values less than 2.
        This is because the highest possible product with only 4 digits within the slide is 9*9*9*9 = 6561. So, simply dividing 15552/6561 = 2.37... So, in order to get a number higher than 15552 (which we found by inspection), we need to have a digit value higher than 2.37. In conclusion, omitting any calculation of a "slide" containing digit values less than 2 is valid.

#include <stdio.h>
#include <stdlib.h>

#define S_LENGTH 1000

int main()
{
    char *s = "73167176531330624919225119674426574742355349194934"
                "96983520312774506326239578318016984801869478851843"
                "85861560789112949495459501737958331952853208805511"
                "12540698747158523863050715693290963295227443043557"
                "66896648950445244523161731856403098711121722383113"
                "62229893423380308135336276614282806444486645238749"
                "30358907296290491560440772390713810515859307960866"
                "70172427121883998797908792274921901699720888093776"
                "65727333001053367881220235421809751254540594752243"
                "52584907711670556013604839586446706324415722155397"
                "53697817977846174064955149290862569321978468622482"
                "83972241375657056057490261407972968652414535100474"
                "82166370484403199890008895243450658541227588666881"
                "16427171479924442928230863465674813919123162824586"
                "17866458359124566529476545682848912883142607690042"
                "24219022671055626321111109370544217506941658960408"
                "07198403850962455444362981230987879927244284909188"
                "84580156166097919133875499200524063689912560717606"
                "05886116467109405077541002256983155200055935729725"
                "71636269561882670428252483600823257530420752963450";


    int i, j, greatestProd = 0, prod;

    for (i = 0; i < S_LENGTH-4;i++){
        prod = 1;
        for (j = 0; j < 5; j++){
            prod *= (s[i+j]-'0');
        }
        if (prod > greatestProd)
            greatestProd = prod;
    }
    printf("%d\n", greatestProd);

    return 0;
}

Best Execution Time: 0.007s
Answer:

70824