Product of K digits in an N digit Number

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 a $N$ digit integer.

Output Format

Print the required answer for each test case.

Constraints:

$1 \le T \le 100$

$1 \le K \le 7$

$K \le N \le 1000$

Solution by Arjun Suresh

Complexity: $O (kn)$ <syntaxhighlight lang="c" name="productofkdigits">

1. include<stdio.h>
2. include<string.h>

int main() {

       char array[1001];
       int i, j, l, k, n, num;
       scanf("%d", &num);
       for(i = 0; i < num; i++)
       {
               scanf("%d%d", &n, &k);
               scanf("%s", array);
               unsigned long big = 0;
               for(j = 0; j < strlen(array)-k; j++)
               {
                       unsigned long  product = 1;
                       for(l = j; l < j+k; l++)
                               product *= array[l]-'0';
                       if(product > big)
                               big = product;
               }
               printf("%lu\n", big);
       }

}

</syntaxhighlight>

Extra space can reduce time complexity

Complexity: $O (n)$ <syntaxhighlight lang="c" name="productofkdigits">

1. include<stdio.h>
2. include<string.h>

int main() {

       char array[1001];
       unsigned long prod[1001];
       int i, j, l, k, n, num;
       scanf("%d", &num);
       for(i = 0; i < num; i++)
       {
               scanf("%d%d", &n, &k);
               scanf("%s", array);
               unsigned long big = 0;
               prod[0] = array[0]-'0';
               for(j = 1; j < strlen(array); j++)
               {
                       if(j < k)
                               prod[j] = prod[j-1]*(array[j]-'0');
                       else
                               prod[j] = prod[j-1]*(array[j]-'0')/prod[j-k];
                       if(prod[j] > big)
                               big = prod[j];
               }
               printf("%lu\n", big);
       }

} </syntaxhighlight>

Tweet