Project Euler #8 in C++: greatest product of k consecutive digits This a problem from Hackerrank.com and Project Euler #8. The problem statement is as below. Is there a specific algorithm to solve such problems? Can my code be made more efficient?




  Find the greatest product of K consecutive digits in the N digit
  number.
  
  Input Format: First line contains T that denotes the number of test cases.  First line of each test case will contain two integers
  N &amp; K. Second line of each test case will contain an N digit
  integer. 
  
  Output Format
  
  Print the required answer for each test case.
  
  Constraints 
  
  \$1 \le T \le 1000\$
  
  \$1 \le K \le 7\$
  
  \$K \le N \le 1000\$




#include &lt;cmath&gt;
#include &lt;cstdio&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;
using namespace std;
#define ctoi(c)(int)((c)-'0')

inline unsigned long long prodK(string number, int start, int end){
    unsigned long long product=1;
    for (int j=start;j&lt;end;j++){
        product*=ctoi(number[j]);
    }
    return product;
}

int main() {
    int T,N,K;
    string number;
    unsigned long long product,max;
    cin&gt;&gt;T;
    for (int i=0;i&lt;T;i++){
        cin&gt;&gt;N&gt;&gt;K;
        cin&gt;&gt;number;
        product=1;
        product=prodK(number,0,K);
        max=product;
        for (int l=K;l&lt;N;l++){
            if (ctoi(number[l-K])!=0){
                product=(product/ctoi(number[l-K]))*ctoi(number[l]);
            }else{
                product=prodK(number,l-K+1,l+1);
            }
            max=(product&gt;max)?product:max;
        }
        cout&lt;&lt;max&lt;&lt;"\n";
    }
    return 0;
}
Extra multiplication


    unsigned long long product=1;
    for (int j=start;j&lt;end;j++){
        product*=ctoi(number[j]);
    }



You can do one less multiplication.  

    unsigned long long product = ctoi(number[j]);
    for (int j = start + 1; j &lt; end; j++) {
        product *= ctoi(number[j]);
    }


Obviously this would fail if K were less than 1, but that's outside the problem scope.  

ctoi is not a free operation

You also perform ctoi at least K times for each digit.  You could do this just once with something like 

    std::vector&lt;int&gt; digits;
    for (char c : number) {
        digits.push_back((int)(c - '0');
    }


Then operate on digits rather than number.  

Benchmark optimizations


            if (ctoi(number[l-K])!=0){
                product=(product/ctoi(number[l-K]))*ctoi(number[l]);
            }else{
                product=prodK(number,l-K+1,l+1);
            }



In theory, this saves K-1 multiplications at the cost of doing a multiplication, a division, and a comparison/branch.  But don't forget that it adds a comparison/branch to every iteration.  You might find that is cheaper to always do the K-1 multiplications.  

Benchmark it both ways with a variety of inputs to see.  

Don't waste math

You have 


    for (int j=start;j&lt;end;j++){



and 


                    product=prodK(number,l-K+1,l+1);



But you could just have 


    for (int j = start; j &lt;= end; j++){



and 

                    product = prodK(number, l-K+1, l);


That saves you an addition.  Might not be worth much, but it also might be better than nothing.  

Assignments can be expensive


            max=(product&gt;max)?product:max;



This will produce the correct answer, but it does an assignment every time.  You don't need to do the no-op assignment.  Benchmark against 

            if (product &gt; max) {
                max = product;
            }


That's more code, but it's faster unless the compiler already optimizes out the no-op assignment.  Probably not a lot faster, as this is a comparatively simple assignment.  

Simplify compare


    for (int i=0;i&lt;T;i++){



i&lt;T is often implemented as i - T &lt; 0.  But do you need to do the i - T?

Since you never use T for anything other than this loop, you could say 

    for (; T &gt; 0; T--) {


That saves having an i variable at all, and now you compare T to 0 directly.  

Benchmark

These are suggestions that assume that the compiler is operating in a certain way.  If I'm wrong about that, then some of these suggestions may be counterproductive.  Note that the compiler may have similar or better optimizations that it is already doing.  You benchmark to confirm (or refute) such assumptions.