title: figure out Uneaten Leaves algorithm bug
body: <p>I faced this problem in an interview challenge</p>
  <blockquote>
  <p>K caterpillars are eating their way through N leaves, each caterpillar
  falls from leaf to leaf in a unique sequence, all caterpillars start
  at a twig at position 0 and falls onto the leaves at position between
  1 and N. Each caterpillar j has an associated jump number Aj. A
  caterpillar with jump number j eats leaves at positions that are
  multiple of j. It will proceed in the order j, 2j, 3j…. till it
  reaches the end of the leaves and it stops and build its cocoon. Given
  a set A of K elements , we need to determine the number
  of uneaten leaves.</p>
  <p><strong>Constraints:</strong></p>
  <p>1 &lt;= N &lt;= 10<sup>9</sup></p>
  <p>1 &lt;= K &lt;= 15</p>
  <p>1 &lt;= A[i] &lt;= 10<sup>9</sup></p>
  <p><strong>Input format:</strong></p>
  <p>N = No of uneaten leaves.</p>
  <p>K = No. of caterpillars.</p>
  <p>A = Array of integer.
  jump numbers Output:</p>
  <p>The integer nu. Of uneaten leaves</p>
  <p><strong>Sample Input:</strong></p>
  <p><code>10</code><br>
  <code>3</code> <br>
  <code>2</code> <br>
  <code>4</code> <br>
  <code>5</code><br></p>
  <p><strong>Output:</strong></p>
  <p><code>4</code></p>
  <p><strong>Explanation:</strong></p>
  <p>[2, 4, 5] is the 3-member set of jump numbers. All leaves which are multiple of 2, 4, and 5 are eaten. Only 4 leaves which are numbered 1,3,7,9 are left.</p>
  </blockquote>
  <p>the naive approach for solving this question is have a <em>Boolean</em> array of all N numbers, and iterate over every caterpillar and remember the eaten leaves by it. <br></p>
  <pre><code>int uneatenusingNaive(int N, vector&lt;int&gt; A)
  {
      int eaten = 0;
      vector&lt;bool&gt;seen(N+1, false);
      for (int i = 0; i &lt; A.size(); i++)
      {
          long Ai = A[i];
          long j = A[i];
          while (j &lt;= N &amp;&amp; j&gt;0)
          {
              if (!seen[j])
              {
                  seen[j] = true;
                  eaten++;
              }
              j += Ai;
          }
      }
      return N - eaten;
  }
  </code></pre>
  <p>this approach passed 8 out of 10 test cases and give wrong answer for 2 cases.<br>
  <br>
  another approach using <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle%22Inclusion%20Exclusion%20principle%22" rel="nofollow noreferrer">Inclusion Exclusion principle</a>, explanation for it can be found <a href="https://stackoverflow.com/questions/27248327/caterpillars-and-leaves-can-we-do-better-than-onc">here</a> and <a href="http://www.iarcs.org.in/inoi/contests/sep2004/Advanced-2-solution.php" rel="nofollow noreferrer">here</a> <br>
  below is my code for the second approach</p>
  <pre><code> int gcd(int a, int b)
      {
          if (b == 0)
              return a;
          return gcd(b, a%b);
      }
      int lcm(int i, int j)
      {
          return i*j / gcd(i, j);
      }
      
      vector&lt;vector&lt;int&gt;&gt; mixStr(vector&lt;vector&lt;int&gt;&gt; &amp; mix, vector&lt;int&gt;&amp; A, unordered_map&lt;int, int&gt; &amp; maxStart)
      {
          vector&lt;vector&lt;int&gt;&gt; res;
          if (mix.size() == 0)
          {
              for (int i = 0; i &lt; A.size(); i++)
              {
                  vector&lt;int&gt; tmp;
                  tmp.push_back(A[i]);
                  res.push_back(tmp);
              }
              return res;
          }
          
          
          for (int i = 0; i&lt;mix.size(); i++)
          {
              int currSlotSize = mix[i].size();
              int currSlotMax = mix[i][currSlotSize - 1];
              
              for (int j = maxStart[currSlotMax]; j &lt; A.size(); j++)
              {
                  vector&lt;int&gt; tmp(mix[i]);
                  tmp.push_back(A[j]);
                  res.push_back(tmp);
              }
          }
          return res;
      }
      int uneatenLeavs(int N, int k, vector&lt;int&gt; A)
      {
          int i = 0;
          vector&lt;vector&lt;int&gt;&gt; mix;
          bool sign = true;
          int res = N;
          sort(A.begin(), A.end());
          unordered_map&lt;int,int&gt; maxStart;
          for (int i = 0; i &lt; A.size(); i++)
          {
              maxStart[A[i]] = i + 1;
          }
          int eaten = 0;
          
      
          while (mix.size() != 1)
          {   
              
              mix = mixStr(mix, A, maxStart);
              for (int j = 0; j &lt; mix.size(); j++)
              {
                  int _lcm = mix[j][0];
                  for (int s = 1; s &lt; mix[j].size(); s++)
                  {
                      _lcm = lcm(mix[j][s], _lcm);
                  }
                  if (sign)
                  {
                      res -= N / _lcm;
                  }
                  else
                  {
                      res += N / _lcm;
                  }
              }
              sign = !sign;
              i++;
          }
          return res;
      }
  </code></pre>
  <p>this approach passed only one 1/10 test case. and for the rest of test cases time limit exceeded and wrong answer. <br> <br>
  <strong>Question:</strong> <br>
  What am I missing in first or second approach to be 100% correct.</p>