Calculating number of unharmed leaves I recently came across this problem that asks you to print the number of leaves not eaten by the caterpillars:


  As we all know caterpillars love to eat leaves. Usually, a caterpillar
  sits on leaf, eats as much of it as it can (or wants), then stretches
  out to its full length to reach a new leaf with its front end, and
  finally "hops" to it by contracting its back end to that leaf.
  
  We have with us a very long, straight branch of a tree with leaves
  distributed uniformly along its length, and a set of caterpillars
  sitting on the first leaf. (Well, our leaves are big enough to
  accommodate upto 20 caterpillars!). As time progresses our
  caterpillars eat and hop repeatedly, thereby damaging many leaves. Not
  all caterpillars are of the same length, so different caterpillars may
  eat different sets of leaves. We would like to find out the number of
  leaves that will be undamaged at the end of this eating spree. We
  assume that adjacent leaves are a unit distance apart and the length
  of the caterpillars is also given in the same unit.
  
  For example suppose our branch had 20 leaves (placed 1 unit apart) and
  3 caterpillars of length 3, 2 and 5 units respectively. Then, first
  caterpillar would first eat leaf 1, then hop to leaf 4 and eat it and
  then hop to leaf 7 and eat it and so on. So the first caterpillar
  would end up eating the leaves at positions 1,4,7,10,13,16 and 19. The
  second caterpillar would eat the leaves at positions
  1,3,5,7,9,11,13,15,17 and 19. The third caterpillar would eat the
  leaves at positions 1,6,11 and 16. Thus we would have undamaged leaves
  at positions 2,8,12,14,18 and 20. So the answer to this example is 6.


Fortunately, the question is easy and can put a workable code in a decent time. The problem is that it is probably taking more memory than expected, because all the test cases run fine in my PC, but one of them gives a runtime error when run on the servers. How can this be improved?

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    for(int i=0;i&lt;k;i++){
        for(int j=0;caterpillars[i]*j +1 &lt;= n;j++){
            int temp = caterpillars[i] * j +1;
            v.push_back(temp);
        }
    }
    sort(v.begin(),v.end());
    int number = 0;
    long long prev = 0;
    for(int i=0;i&lt;v.size();i++){
        if(v[i] != prev){
            number++;
        }
        prev = v[i];
    }
    std::cout &lt;&lt; n - number &lt;&lt; std::endl;
    return 0;
}


And here is that particular testcase which is causing problems:

762744433 19
96412 40852 19611 563380 236733 559627 750968 413673 300332 65 682403 441221 180068 668364 493413 443706 613246 715846 728157
Uses too much memory, and too much time

Your current solution works but uses too much memory.  The problem requirement specifies maximum 16 MB memory to be used.  Your program uses 4 bytes for each number reached including duplicates.  Given the maximum n of 1000000000, maximum caterpillars of 20, and worst case of each caterpillar having value 2, your program would require 40 GB of memory to solve that case.

Also, your program takes too long to run.  Given the worst case scenario mentioned above, your program would need to iterate 10 billion times.  Even at a rate of 1 billion iterations per second, that would take 10 seconds and your time limit is 3.

I will describe some incremental improvements to your solution to fix the memory issue, and then describe a completely different approach that solves the time issue as well.

Slightly better: use sieve approach

Instead of adding reached numbers to a vector and then sorting, you can do better by creating a std::bitset or vector&lt;bool&gt; to store which numbers were reached.  For example, you could create a vector&lt;bool&gt; of size n+1, and then as you reach each number, you set reached[num] = true.  At the end, you scan the vector to count many numbers are unreached.  Assuming that vector&lt;bool&gt; uses 1 bit per element, this solution requires 125 MB of memory, which is still larger than permitted.  However, this at least won't crash your computer if you run it.  Here is a sample solution:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    std::vector&lt;bool&gt; reached(n);
    for(int i=0;i&lt;k;i++){
        int val = caterpillars[i];
        for(int j=0;j &lt; n;j+= val) {
            reached[j] = true;
        }
    }
    int unreached = 0;
    for(int j=0;j &lt; n;j++) {
        if (!reached[j])
            unreached++;
    }
    std::cout &lt;&lt; unreached &lt;&lt; std::endl;
    return 0;
}


This program solved the "tough case" 762744433 19 ... in 0.9 seconds on my computer.  However, on the worst case of 1000000000 20 2 2 2 2 ..., it took 16 seconds to solve, which exceeds the time limit of 3 seconds.

Next improvement: use fixed amount of memory

To keep your program within the 16 MB memory limit, you need to do the sieving in segments instead of all at once.  For example, you can compute the solution in segments of 1000000, using only 125 KB of memory for the vector&lt;bool&gt;.  Here is an example of how you can do that:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

#define BUFSIZE        1000000

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    std::vector&lt;bool&gt; reached(BUFSIZE);
    int unreached = 0;
    for(int i=0;i&lt;n;) {
        int size = n-i;
        if (size &gt; BUFSIZE)
            size = BUFSIZE;
        std::fill(reached.begin(), reached.end(), false);
        for (int j=0;j&lt;k;j++) {
            int val = caterpillars[j];
            int first = (i % val);
            if (first != 0)
                first = val - first;
            for (int r = first; r &lt; size; r += val)
                reached[r] = true;
        }
        for (int r = 0; r &lt; size; r++) {
            if (!reached[r])
                unreached++;
        }
        i += size;
    }
    std::cout &lt;&lt; unreached &lt;&lt; std::endl;
    return 0;
}


Similar to the previous program, this program also solved the "tough case" in 0.9 seconds.  It took 14 seconds to solve the worst case, though.  Although there are some optimizations that could be made, it seems that a new algorithm might be needed.

A different approach

This problem is somewhat reminiscent of the FizzBuzz problem.  In FizzBuzz, each number divisible by 3 is Fizz, each number divisible by 5 is Buzz, and each number divisible by both 3 and 5 is FizzBuzz.  If I asked how many numbers between 1 and n are one of Fizz/Buzz/FizzBuzz, you could come up with a \$O(1)\$ solution instead of an \$O(n)\$ solution.

If you think about it a little, n/3 numbers are either Fizz or FizzBuzz, and n/5 numbers are either Buzz or FizzBuzz, and n/15 numbers are FizzBuzz.  So the count of "named" numbers is n/3 + n/5 - n/15.

You can transfer this approach to the caterpillar problem.  Given 2 caterpillars of length a b, the number of leaves eaten is n/a + n/b - n/lcm(a,b), where lcm() is the least common multiple of a and b.

Now you can extend the approach for 3 caterpillars.  With three caterpillars of length a b c, you can have leaves eaten by a, b, c, ab, bc, ac, or abc, where ab means eaten by both a and b.  After doing some reasoning on this, you would come up with the formula:

Leaves eaten = n/a + n/b + n/c - n/lcm(a,b) - n/lcm(b,c) - n/lcm(a,c) + n/lcm(a,b,c)

The formula generalizes to:

Leaves eaten = Sum(n/one) - Sum(n/two) + Sum(n/three) - Sum(n/four) + Sum(n/five) - ...

where Sum(n/five) means the sum of all combinations of the form n/lcm(five caterpillars).

To solve using this method, you need to generate each combination of caterpillars.  With 20 caterpillars, this means you need to go through each of the \$2^{20}\$ combinations, which is actually only 1 million combinations so it should complete quickly.  In general, with \$k\$ caterpillars, this solution solves the problem in \$O(2^k)\$ time.  So you definitely do not want to use this solution with a large number of caterpillars.

I wrote a sample solution that used recursion to generate each combination.  The solve() function tries two cases: including the current caterpillar or not including it, and recurses to the next caterpillar for each case.  You can easily see that this generates 2^k cases.

Here is my solution using this approach:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

// Returns greatest common divisor of a and b.
static inline int gcd(int a, int b)
{
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

// Returns least common multiple of a and b.
static inline long long lcm(int a, int b)
{
    a /= gcd(a, b);
    return (long long) a * b;
}

static int solve(std::vector&lt;int&gt; caterpillars, int curCaterpillar,
        int numUsed, int curLcm, int n)
{
    if (curCaterpillar &gt;= caterpillars.size())
        return 0;

    int val = caterpillars[curCaterpillar];
    int reached = 0;

    // Include current caterpillar:
    long long newLcm = lcm(curLcm, val);
    if (newLcm &lt;= n) {
        if (numUsed &amp; 1)
            reached -= n / newLcm;
        else
            reached += n / newLcm;
        reached += solve(caterpillars, curCaterpillar+1, numUsed+1, newLcm, n);
    }

    // Do not include current caterpillar:
    reached += solve(caterpillars, curCaterpillar+1, numUsed, curLcm, n);

    return reached;
}

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    int reached = 0;

    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    n--;
    reached = solve(caterpillars, 0, 0, 1, n);
    std::cout &lt;&lt; n - reached &lt;&lt; std::endl;
    return 0;
}


This solution solved the "tough case" in 0.01 seconds on my computer, and solved the "worst case" in 0.46 seconds.

There are further optimizations that could be made, such as filtering out caterpillars that are multiples of each other before starting the algorithm.  Such caterpillars can be removed without changing the result.  Using that optimization, the worst time I got for any input I tried was 0.08 seconds.