The second term gives you \sum d_i \mod 10 \mod 3, and you need \sum d_i \mod 3.
yes. thanks for confirming.
My Short solution in PYTHON 3.5:-Time Complexity O(1)
test=int(input()) for y in range(test): k,dig0,dig1=input().split() k,dig0,dig1=int(k),int(dig0),int(dig1) sum1=dig0+dig1 for i in range(3,k+2): y=sum1%10 sum1+=y if(y==2): ter1=((k-i)//4) ter1*=20 sum1+=ter1 ter=k-i if(ter%4==3): sum1+=18 elif(ter%4==2): sum1+=12 elif(ter%4==1): sum1+=4 break if(y==0): break if(sum1%3==0): print("YES") else: print("NO")
For a number to be divisible by Three sum should be divisisble by 3.Keep on adding sum and finding digits(sum%10); if digit is 0 then break as sum will remain same even after u do any operation so break. Else break when u find a two as 2,4,8,6 block will keep on repeating. therefore add ((k-i)//4)(2+4+6+8) to sum ((k-i)//4) is floor division plus remaining 4 12 or 18 depending on whether 4 or 4,8 or 4,8,6 is remaining. This block’s size is got by (k-i)%4.Then at last check whether sum is divisible by 3.
Thanks for posting the editorial, but I am really at a loss why my solution is failing. I tried all possible boundary cases as well as some that tested big values.
If you could give me a fail case for the below code, and also help me out on how you tested this solution, it will be really helpful.
4 2 5
Thanks for your response. However I see that the number generated by 4 2 5 is 2574. Which is divisible by 3 as per my output, and it is also divisible by 3. Please let me know if I’m wrong somewhere.
my method https://www.codechef.com/viewsolution/22144353 is by observation of repeating digits, with refer to example 2, N is 8198624862486 which is 819 8624 8624 86, which mean that for k = 13, we try to find how many repeated sequence behind 819, which is (13-3)/4 = 2 and (13-3)%4 = 2 , that mean i sum up 8+1+9 + 2*(8+6+2+4) + (8+6) = 72, since 72%3==0, that mean example 2 answer is “YES”.