Largest product in a series (problem 8)

Posted: 27/06/2013 in Project Euler
Tags: , , ,

Problem 8 of PE’s website says:

Find the greatest product of five consecutive digits in the 1000-digit number:

73167176531330624919225119674426574742355349194934\\  96983520312774506326239578318016984801869478851843\\  85861560789112949495459501737958331952853208805511\\  12540698747158523863050715693290963295227443043557\\  66896648950445244523161731856403098711121722383113\\  62229893423380308135336276614282806444486645238749\\  30358907296290491560440772390713810515859307960866\\  70172427121883998797908792274921901699720888093776\\  65727333001053367881220235421809751254540594752243\\  52584907711670556013604839586446706324415722155397\\  53697817977846174064955149290862569321978468622482\\  83972241375657056057490261407972968652414535100474\\  82166370484403199890008895243450658541227588666881\\  16427171479924442928230863465674813919123162824586\\  17866458359124566529476545682848912883142607690042\\  24219022671055626321111109370544217506941658960408\\  07198403850962455444362981230987879927244284909188\\  84580156166097919133875499200524063689912560717606\\  05886116467109405077541002256983155200055935729725\\  71636269561882670428252483600823257530420752963450\\

This problem can only be done by using brute force, so here we go.
I provided a general solution in C. My program waits an entering number from the standard input, and then it performs the task. The user also provides as parameters the number of digits of its entering number and the N consecutive digits he/she wants the program to use (in this case it will be 5), in this right order.

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

void charArrToIntArr (char from[], int to[], int length){

    int i = 0;

    for (i = 0; i < length; i++){
      	to[i] = from[i] - 48;
      	/* "ASCII value of a number" - 48 = "the number itself" */
    }
}

int findLargestProduct (int big_number[], int size, int n_consecutive){
    
    int i = 0, j = 0;
    int product = 1;
    int largest_product = 1;

    while (n_consecutive <= size){
      	for (j = i; j < n_consecutive; j++){
         	product *= big_number[j];
      	}
      	n_consecutive++;
      	if (largest_product <= product){
         	largest_product = product;
      	}
     	product = 1; i++;
    }

    return largest_product;
}

int main (int argc, char *argv[]){

    const unsigned int size_max = (unsigned int) atoi (argv[1]);
    int n_consecutive = atoi (argv[2]);

    char * big_number_temp = malloc (size_max * sizeof (char));
    int big_number[size_max];

    int i = 0;
    
    while (!feof (stdin)){
      	scanf ("%c", &big_number_temp[i]);
      	if (!feof (stdin)){	    
         	if (big_number_temp[i] == '\n'){
            	i--;
         	}
            i++;

         	if (i == size_max){
            	fprintf (stderr, "\nWarning: Array's limit reached (at %d).\n", i);
            	break;
         	}
    	}
    } 

    charArrToIntArr (big_number_temp, big_number, i);
    free (big_number_temp);

    printf ("%d\n", findLargestProduct (big_number, i, n_consecutive));

    return 0;
}

Finally,

$ (gcc -Wall -Wconversion prob8.c) && ./a.out 1000 5
# (Ctrl + Shift + v)
40824

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s