< Back to forum

in CODECHEF:MULTHREE (multiple of 3) ...my code is running in small inputs and giving right output in codeblocks but my code gives runtime error in large input and i already tried long long int and unsigned long long too...

#include<stdio.h>

int main()
{
int t,j,d0,d1,s;
long long int k,i,l;
scanf("%d",&t);

while(t--)
{
scanf("%lld %d %d",&k,&d0,&d1);
long long int a[k];
a[0]=d0;
a[1]=d1;

for(i=2;i<k;i++)
{
s=0;
for(l=0;l<i;l++)
{
s=s+a[l];
}
s=s%10;
a[i]=s;
}


int m=0;
for(i=0;i<k;i++)
{
    m=m+(a[i]%3);
}

if(m%3==0)
    printf("Yes\n");
else
   printf("No\n");


}



return 0;
}

 

codechef multhree

Asked by: Manish_Kumar_Savita on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

Let me first help you with the data types. You need long long int to hold k. But you need only int to hold elements of a[k] as each of its elements will be 0 to 9 (remember it is given %10).

Coming to your logic, think if you really need to construct the array a[] in this problem. I don't think so.

Next, you need to use modulo property (a+b)%M = (a%M + b%M)%M to solve this question. Since the time limit is 1 sec and value of k~= 10^12, you cannot use two nested loops. You need to use only one loop to calculate the rest of K-2 elements (which you MAY need not store in an array) from d0 and d1. Also figure out how you can apply this modulo property inside your loop.

Next, to calculate the sum of digits, you can add an extra line inside the first loop only. Think of a more optimized logic. Much hints given in this answer.

Siddharth_Garg last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.