Hello I was doing MULTHREE question on CodeChef could anyone please help me why I am getting the Wrong answer

My logic - since every digit from 3rd digit onwards is equal to the sum of the previous digits mod 10.

and a number is divisible by 3 if its sum of the digit is divisible by 3.

The sum of all k digits of a number is given by

s = (2^(k-2)-1)X((d0+d1)%10) + (d0+d1)

Therefore,

s%3 = ((((2^(k-2)%3-1)%3)X(((d0+d1)%10)%3))%3 + (d0+d1)%3)%3

Question Link - https://www.codechef.com/problems/MULTHREE

my code - https://ideone.com/yuVmkF

Thanks.

you must have noted something that next number in sequence starting from 4th one is

(2*unitdigit of previous number)%10

so if we remove corner cases like (d0+d1)%5==0 which will return false except for 15 we can say that

a repeated sequence of 2,4,8,6 will occur so we can find sum till the pattern’s first occurance then we simply add to the sum ((remaining length)/4)*20 and add remaining few numbers of repeated sequence on the basis of len=(remaining length)%4

if len =1 we add 2

if len =2 we add 6

if len =3 we add 14

i hope you get the idea i want to tell here

1 Like

Yea I got this idea thanks bro. I also realized my formula which i wrote for s is not correct.