Project Euler #8 - Largest product in a sequence I've just finished Project Euler Problem 8, which ask for the greatest product of any sequence of 13 consecutive digits in a given string.

I wonder if there's something that could be improved.



function EulerProblem8() {

 var amountOfDigits = 13;
 var sequence = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
 var highestSum = 0;
 var firstIndx = 0;
 var lastIndx = firstIndx + amountOfDigits;
 
 while(lastIndx != sequence.length)
 {
  var substr = sequence.substring(firstIndx, lastIndx);
  var array = substr.split('');
  
  var sum = 1;
  for(var c in array) {
   var i = array[c] * 1.0;
   
   sum = sum * i;
  }
  
  if(sum &gt; highestSum)
   highestSum = sum;
   
  firstIndx = firstIndx + 1;
  lastIndx = firstIndx + amountOfDigits;
 }
 
 document.getElementById('output').innerHTML = "Result: " + highestSum;
}

EulerProblem8();
&lt;pre id="output"&gt;...working...&lt;/pre&gt;
There are some obvious items, and then some not-so-obvious ones, that should be addressed.

The most obvious, is this line here:

sum = sum * i;


Really? That's a sum. Don't you mean product?

The next obvious item is that the function should take the number of digits, and the input sequence, as parameters. I would expect a function like:

function eulerProblem8(span, digits) {
    ....


and then the function returns the largest value.

Now, about the algorithm, this is more complicated. There is a way to do it in \$O(n)\$ time complexity. You can scan all the data just once, with a zero-counter, and multiplication and division.


scan each position in the input
if your sequence will be longer than the span, remove the unneeded digit using division (if the value is non-zero - or decreasing the zero-counter if the value is zero).
if the next value in the sequence is zero, increment the zero counter, otherwise include the digit by mutiplying the product.
if the new product is larger than previous products, then remember this new maximum
report the maximum.


Consider the following....



function eulerProblem8(span, sequence) {

    var follow = -1;
    var zeroes = 0;
    var maxprod = 0;
    var prod = 1;
    var digit;
  
    for (var lead = 0; lead &lt; sequence.length; lead++) {

      // determine the least digit
      if (lead - follow &gt; span) {
        follow = lead - span;
      }

      if (follow &gt;= 0) {
        // remove least digit
        digit = Number(sequence[follow]);
        if (digit == 0) {
          zeroes--;
        } else {
          prod /= digit;
        }
      }

      // include the next digit
      digit = Number(sequence[lead]);
      if (digit == 0) {
        zeroes++;
      } else {
        prod *= digit;
      }

      // if there are no zeros in the sequence, and it exceeds previous...
      if (zeroes == 0 &amp;&amp; prod &gt; maxprod) {
        maxprod = prod;
      }
    }

    return maxprod;
}

var amountOfDigits = 13;
var sequence = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"

document.getElementById('result').innerHTML = "Max: " + eulerProblem8(amountOfDigits, sequence);
&lt;p id="result"&gt;result&lt;/p&gt;
&lt;pre id="debug"&gt;unused&lt;/pre&gt;