what function choose(x,y) does?
@akumar3 : I saw your solution for this problem.
https://www.codechef.com/viewsolution/5863202
Can you tell why have you incremented curr when i = 0 in processResult() ?
That is because the case with 0 remainder is special.
For every two prefixes with equal remainder, we have 1 substring which is divisible by 3;
Now consider following string:
33
Prefixes:
3, 33 (both gives remainder 0 when divided by 3)
If you apply above formula, you will get ‘1’ substring which is divisible by 3.
But here both the original prefixes are also divisible by 3.
To account this fact, we have to update our formula for the case when remainder is 0, so if we have N prefixes which gives remainder 0; our answer will be:
= (N(N-1))/2 + N (original prefixes)
= (N*(N+1))/2
1 Like
how could i modify this to check if the substring between C and D inclusive is divisible by 3 ??
Or am i trying to explore a wrong approach for doing this ?
#include <stdio.h>
int main()
{
int rows, cols, i, j;
/*
* Reads number of rows, columns to be printed
*/
printf("Enter number of rows: ");
scanf("%d", &rows);
printf("Enter number of columns: ");
scanf("%d", &cols);
for(i=1; i<=rows; i++)
{
for(j=1; j<=cols; j++)
{
//Print 1 if its first or last row
//Print 1 if its first or last column
if(i==1 || i==rows || j==1 || j==cols)
{
printf("*");
}
else
{
printf(" ");
}
}
printf("\n");
}
return 0;
}