Find the greatest product of five consecutive digits in the 1000-digit number.
7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450To do brute force calculation, logic is easy but kind of having bad performance. To practice and brainstorming some good algorithms to boost the checking speed can be ultimate fun in solving problems we faced.
My strategy is to check whether we can safely eliminate any 5 digits with 0 inside (which is obvious), then check for 1, 2, 3, till 9. comparing integer values must be much faster than multiply operations, not mention in thousands.
Below is my code, not polished yet, just to illustrate my ideas. My intention is not to show off my code but to ignite better ideas and faster solutions.
int main() { char l_arIntegers[1001] = { "73167176531330624919225119674426574742355349194934\ 96983520312774506326239578318016984801869478851843\ 85861560789112949495459501737958331952853208805511\ 12540698747158523863050715693290963295227443043557\ 66896648950445244523161731856403098711121722383113\ 62229893423380308135336276614282806444486645238749\ 30358907296290491560440772390713810515859307960866\ 70172427121883998797908792274921901699720888093776\ 65727333001053367881220235421809751254540594752243\ 52584907711670556013604839586446706324415722155397\ 53697817977846174064955149290862569321978468622482\ 83972241375657056057490261407972968652414535100474\ 82166370484403199890008895243450658541227588666881\ 16427171479924442928230863465674813919123162824586\ 17866458359124566529476545682848912883142607690042\ 24219022671055626321111109370544217506941658960408\ 07198403850962455444362981230987879927244284909188\ 84580156166097919133875499200524063689912560717606\ 05886116467109405077541002256983155200055935729725\ 71636269561882670428252483600823257530420752963450"}; char* pIntegers = (char *)l_arIntegers; int l_iarMaxWithIdx[10] = {0, 9*9*9*9*1, 9*9*9*9*2, 9*9*9*9*3, 9*9*9*9*4, 9*9*9*9*5, 9*9*9*9*6, 9*9*9*9*7, 9*9*9*9*8, 9*9*9*9*9}; int l_iMaxProduct = 1; int l_iEliminate = -1; for(int m = 0; m < 10; m++) { std::cout << "now check for m = " << m << ", Eliminate = " << l_iEliminate << " and max product " << l_iarMaxWithIdx[m] << " and current max product as " << l_iMaxProduct << std::endl; //check whether we can eliminate 1s if(l_iMaxProduct > l_iarMaxWithIdx[m]) { //we can safely eliminate ms already. l_iEliminate += 1; continue; } bool l_bReachEnd = false; for(int i = 4; i < 20 * 51;) { if(pIntegers[i] - '0' <= l_iEliminate) { i += 5; if(i >= 1001) l_bReachEnd = true; } else if(pIntegers[i - 1] - '0' <= l_iEliminate) { i += 4; if(i >= 1001) l_bReachEnd = true; } else if(pIntegers[i - 2] - '0' <= l_iEliminate) { i += 3; if(i >= 1001) l_bReachEnd = true; } else if(pIntegers[i - 3] - '0' <= l_iEliminate) { i += 2; if(i >= 1001) l_bReachEnd = true; } else if(pIntegers[i - 4] - '0' <= l_iEliminate) { i += 1; if(i >= 1001) l_bReachEnd = true; } else { if(i >= 1000) l_bReachEnd = true; //none of previous 5 is 0 //check for any sum is greater than 9*9*9*9*1 int l_iProduct = (pIntegers[i] - '0') * (pIntegers[i-1] - '0') * (pIntegers[i-2] - '0') * (pIntegers[i-3] - '0') * (pIntegers[i-4] - '0'); std::cout << "now check for m = " << m << " and current product = " << l_iProduct << " with current max product as " << l_iMaxProduct << std::endl; if(l_iProduct > l_iMaxProduct) l_iMaxProduct = l_iProduct; if(l_iProduct > l_iarMaxWithIdx[m]) { //we can safely eliminate 1s now std::cout << "current continuous values are " << pIntegers[i-4] << pIntegers[i-3] << pIntegers[i-2] << pIntegers[i-1] << pIntegers[i] << std::endl; l_iEliminate += 1; i = 20 * 51; } i += 1; } } if(l_bReachEnd) { //no need to search again, we find the maximum std::cout << "reach end before checking for " << (m+1) << ", max product = " << l_iMaxProduct << std::endl; break; } } std::cout << "max product = " << l_iMaxProduct << std::endl; return 0;
}
$ time a.out
now check for m = 0, Eliminate = -1 and max product 0 and current max product as 1
now check for m = 1, Eliminate = 0 and max product 6561 and current max product as 1
now check for m = 1 and current product = 882 with current max product as 1
now check for m = 1 and current product = 126 with current max product as 882
now check for m = 1 and current product = 294 with current max product as 882
now check for m = 1 and current product = 1764 with current max product as 882
now check for m = 1 and current product = 1470 with current max product as 1764
now check for m = 1 and current product = 630 with current max product as 1764
now check for m = 1 and current product = 630 with current max product as 1764
now check for m = 1 and current product = 270 with current max product as 1764
now check for m = 1 and current product = 135 with current max product as 1764
now check for m = 1 and current product = 432 with current max product as 1764
now check for m = 1 and current product = 648 with current max product as 1764
now check for m = 1 and current product = 648 with current max product as 1764
now check for m = 1 and current product = 324 with current max product as 1764
now check for m = 1 and current product = 180 with current max product as 1764
now check for m = 1 and current product = 180 with current max product as 1764
now check for m = 1 and current product = 20 with current max product as 1764
now check for m = 1 and current product = 90 with current max product as 1764
now check for m = 1 and current product = 270 with current max product as 1764
now check for m = 1 and current product = 378 with current max product as 1764
now check for m = 1 and current product = 1512 with current max product as 1764
now check for m = 1 and current product = 6048 with current max product as 1764
now check for m = 1 and current product = 1344 with current max product as 6048
now check for m = 1 and current product = 1344 with current max product as 6048
now check for m = 1 and current product = 960 with current max product as 6048
now check for m = 1 and current product = 1680 with current max product as 6048
now check for m = 1 and current product = 1680 with current max product as 6048
now check for m = 1 and current product = 5880 with current max product as 6048
now check for m = 1 and current product = 3920 with current max product as 6048
now check for m = 1 and current product = 1568 with current max product as 6048
now check for m = 1 and current product = 672 with current max product as 6048
now check for m = 1 and current product = 840 with current max product as 6048
now check for m = 1 and current product = 600 with current max product as 6048
now check for m = 1 and current product = 450 with current max product as 6048
now check for m = 1 and current product = 900 with current max product as 6048
now check for m = 1 and current product = 2700 with current max product as 6048
now check for m = 1 and current product = 540 with current max product as 6048
now check for m = 1 and current product = 972 with current max product as 6048
now check for m = 1 and current product = 1296 with current max product as 6048
now check for m = 1 and current product = 2916 with current max product as 6048
now check for m = 1 and current product = 972 with current max product as 6048
now check for m = 1 and current product = 3888 with current max product as 6048
now check for m = 1 and current product = 3888 with current max product as 6048
now check for m = 1 and current product = 5832 with current max product as 6048
now check for m = 1 and current product = 5832 with current max product as 6048
now check for m = 1 and current product = 15552 with current max product as 6048
current continuous values are 49698
now check for m = 2, Eliminate = 1 and max product 13122 and current max product as 15552
now check for m = 3, Eliminate = 2 and max product 19683 and current max product as 15552
now check for m = 3 and current product = 6048 with current max product as 15552
now check for m = 3 and current product = 5880 with current max product as 15552
now check for m = 3 and current product = 3920 with current max product as 15552
now check for m = 3 and current product = 900 with current max product as 15552
now check for m = 3 and current product = 2700 with current max product as 15552
now check for m = 3 and current product = 3888 with current max product as 15552
now check for m = 3 and current product = 3888 with current max product as 15552
now check for m = 3 and current product = 5832 with current max product as 15552
now check for m = 3 and current product = 5832 with current max product as 15552
now check for m = 3 and current product = 15552 with current max product as 15552
now check for m = 3 and current product = 11664 with current max product as 15552
now check for m = 3 and current product = 6480 with current max product as 15552
now check for m = 3 and current product = 7560 with current max product as 15552
now check for m = 3 and current product = 7560 with current max product as 15552
now check for m = 3 and current product = 13824 with current max product as 15552
now check for m = 3 and current product = 12096 with current max product as 15552
now check for m = 3 and current product = 12096 with current max product as 15552
now check for m = 3 and current product = 16128 with current max product as 15552
now check for m = 3 and current product = 8960 with current max product as 16128
now check for m = 3 and current product = 3840 with current max product as 16128
now check for m = 3 and current product = 3840 with current max product as 16128
now check for m = 3 and current product = 5760 with current max product as 16128
now check for m = 3 and current product = 11664 with current max product as 16128
now check for m = 3 and current product = 6480 with current max product as 16128
now check for m = 3 and current product = 6480 with current max product as 16128
now check for m = 3 and current product = 3600 with current max product as 16128
now check for m = 3 and current product = 8100 with current max product as 16128
now check for m = 3 and current product = 4500 with current max product as 16128
now check for m = 3 and current product = 6615 with current max product as 16128
now check for m = 3 and current product = 7560 with current max product as 16128
now check for m = 3 and current product = 7560 with current max product as 16128
now check for m = 3 and current product = 3240 with current max product as 16128
now check for m = 3 and current product = 12096 with current max product as 16128
now check for m = 3 and current product = 14112 with current max product as 16128
now check for m = 3 and current product = 2100 with current max product as 16128
now check for m = 3 and current product = 3150 with current max product as 16128
now check for m = 3 and current product = 6300 with current max product as 16128
now check for m = 3 and current product = 10080 with current max product as 16128
now check for m = 3 and current product = 18144 with current max product as 16128
now check for m = 3 and current product = 15552 with current max product as 18144
now check for m = 3 and current product = 15552 with current max product as 18144
now check for m = 3 and current product = 10368 with current max product as 18144
now check for m = 3 and current product = 10368 with current max product as 18144
now check for m = 3 and current product = 10368 with current max product as 18144
now check for m = 3 and current product = 8640 with current max product as 18144
now check for m = 3 and current product = 7776 with current max product as 18144
now check for m = 3 and current product = 810 with current max product as 18144
now check for m = 3 and current product = 1536 with current max product as 18144
now check for m = 3 and current product = 2048 with current max product as 18144
now check for m = 3 and current product = 3072 with current max product as 18144
now check for m = 3 and current product = 4608 with current max product as 18144
now check for m = 3 and current product = 4608 with current max product as 18144
now check for m = 3 and current product = 5760 with current max product as 18144
now check for m = 3 and current product = 6048 with current max product as 18144
now check for m = 3 and current product = 6048 with current max product as 18144
now check for m = 3 and current product = 5400 with current max product as 18144
now check for m = 3 and current product = 15552 with current max product as 18144
now check for m = 3 and current product = 15552 with current max product as 18144
now check for m = 3 and current product = 13608 with current max product as 18144
now check for m = 3 and current product = 40824 with current max product as 18144
current continuous values are 99879
now check for m = 4, Eliminate = 3 and max product 26244 and current max product as 40824
now check for m = 5, Eliminate = 4 and max product 32805 and current max product as 40824
now check for m = 6, Eliminate = 5 and max product 39366 and current max product as 40824
now check for m = 7, Eliminate = 6 and max product 45927 and current max product as 40824
now check for m = 7 and current product = 40824 with current max product as 40824
now check for m = 7 and current product = 31752 with current max product as 40824
now check for m = 7 and current product = 31752 with current max product as 40824
now check for m = 7 and current product = 24696 with current max product as 40824
now check for m = 7 and current product = 28224 with current max product as 40824
now check for m = 7 and current product = 28224 with current max product as 40824
now check for m = 7 and current product = 31752 with current max product as 40824
reach end before checking for 8, max product = 40824
max product = 40824
0.000u 0.001s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
