Posts Tagged ‘series’

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