title: Code Chef DSA Learning Series : Multiple of 3
body: <p>Consider a very long K-digit number N with digits d0, d1, ..., dK-1 (in decimal notation; d0 is the most significant and dK-1 the least significant digit). This number is so large that we can't give it to you on the input explicitly; instead, you are only given its starting digits and a way to construct the remainder of the number.<br></p>
  <p>Specifically, you are given d0 and d1; for each i ≥ 2, di is the sum of all preceding (more significant) digits, modulo 10 — more formally, the following formula must hold: <br></p>
  <p><a href="https://i.stack.imgur.com/J2OcL.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/J2OcL.png" alt="enter image description here" /></a></p>
  <p>Determine if N is a multiple of 3.<br></p>
  <p>Input<br>
  The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  The first and only line of each test case contains three space-separated integers K, d0 and d1.<br>
  Output<br>
  For each test case, print a single line containing the string &quot;YES&quot; (without quotes) if the number N is a multiple of 3 or &quot;NO&quot; (without quotes) otherwise.<br></p>
  <p>Constraints
  1 ≤ T ≤ 1000<br>
  2 ≤ K ≤ 1012<br>
  1 ≤ d0 ≤ 9<br>
  0 ≤ d1 ≤ 9<br>
  Example<br>
  Input:<br>
  3<br>
  5 3 4<br>
  13 8 1<br>
  760399384224 5 1<br></p>
  <p>Output:<br>
  NO<br>
  YES<br>
  YES<br>
  Explanation<br>
  Example case 1: The whole number N is 34748, which is not divisible by 3, so the answer is NO.<br></p>
  <p>Example case 2: The whole number N is 8198624862486, which is divisible by 3, so the answer is YES.<br></p>
  <p>Question Ended
  <br><br>
  In <a href="https://www.codechef.com/LRNDSA01/problems/MULTHREE" rel="nofollow noreferrer">this</a> question, in the example test case given, we have k=760399384224, d0=5, and d1=1. Now we know that a number is multiple of 3 if the sum of it’s digits is a multiple of 3. So applying it here, we separate the number n into 3 parts,<br>
  Part 1: First 3 digits -&gt; 516 , (5+1+6) mod 3 ==0, so rem1 = 0.<br>
  Part 2: Next will be (k-3)/4 times repetition of (2486) ,or,rem2 = ((2+4+8+6)*((k-3)/4))%3= 1<br>
  Part 3: the last (k-3)%4 =1 digits which will be 2 (from 2486 repetition) , so rem3 = 2%3=2<br>
  So the final answer should be (rem1+rem2+rem3)%3</p>
  <p>and I wrote the following code for this logic:</p>
  <pre><code>#include&lt;iostream&gt;
  #define ll long long
  using namespace std;
  int main()
  {
      int t;
      cin&gt;&gt;t;
      while(t--)
      {
           ll k;
           cin&gt;&gt;k;
           int d0,d1;
           cin&gt;&gt;d0&gt;&gt;d1;
           int d2 = (d0+d1)%10;
           int d[4];
           d[0] = (d0+d1+d2)%10;
           d[1] = (2*d[0])%10;
           d[2] = (2*d[1])%10;
           d[3] = (2*d[2])%10;
           ll rem1 = (d0+d1+d2)%3,rem2,rem3=0;
           rem2 = (20*(((k-3)/4)%3))%3;
           ll x = (k-3)%4;
           if(x!=0)
           {
              for(int i=0; i&lt;x; ++i)
              rem3+=d[i];
              rem3 = rem3%3;
           }
           else
               rem3 =0;
           if(k==2)
           {
               rem1 = (d0+d1)%3;
               rem2=0;
               rem3=0;
           }
           if((rem1+rem2+rem3)%3==0)
              cout&lt;&lt;&quot;YES&quot;&lt;&lt;endl;
           else
              cout&lt;&lt;&quot;NO&quot;&lt;&lt;endl;
      }
  }
  
  
  </code></pre>
  <p>Now they’re giving me WA in their test cases. And I cant think of a possible test cases which doesn’t work with this code. So somebody help me out please.</p>