0
\$\begingroup\$

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 & 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 <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
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<end;j++){
        product*=ctoi(number[j]);
    }
    return product;
}

int main() {
    int T,N,K;
    string number;
    unsigned long long product,max;
    cin>>T;
    for (int i=0;i<T;i++){
        cin>>N>>K;
        cin>>number;
        product=1;
        product=prodK(number,0,K);
        max=product;
        for (int l=K;l<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>max)?product:max;
        }
        cout<<max<<"\n";
    }
    return 0;
}
\$\endgroup\$
1
\$\begingroup\$

Extra multiplication

    unsigned long long product=1;
    for (int j=start;j<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 < 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<int> 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<end;j++){

and

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

But you could just have

    for (int j = start; j <= 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>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 > 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<T;i++){

i<T is often implemented as i - T < 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 > 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.

\$\endgroup\$
  • \$\begingroup\$ I wonder if, for a slight bit of optimization, you can check the sum instead of the product and multiply only if the sum exceeds the maximum sum. For large numbers, this may be slightly faster? \$\endgroup\$ – ChatterOne Aug 17 '16 at 7:03
  • \$\begingroup\$ Thank you. This is good insight. I shall try to implement your suggestions and benchmark. \$\endgroup\$ – Lord Loh. Aug 17 '16 at 7:24
  • \$\begingroup\$ @mdfst - will the compiler with -o3 not do things like - for (; T > 0; T--) while generating the binary executable? \$\endgroup\$ – Lord Loh. Aug 17 '16 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.