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
#i

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 to store which numbers were reached. For example, you could create a vector 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 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 
#include 
#include 

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin >> n >> k;
    std::vector caterpillars;
    std::vectorv;
    for(int i=0;i> a;
        caterpillars.push_back(a);
    }
    std::vector reached(n);
    for(int i=0;i<k;i++){
        int val = caterpillars[i];
        for(int j=0;j < n;j+= val) {
            reached[j] = true;
        }
    }
    int unreached = 0;
    for(int j=0;j < n;j++) {
        if (!reached[j])
            unreached++;
    }
    std::cout << unreached << 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. Here is an example of how you can do that:

#include 
#include 
#include 

#define BUFSIZE        1000000

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin >> n >> k;
    std::vector caterpillars;
    std::vectorv;
    for(int i=0;i> a;
        caterpillars.push_back(a);
    }
    std::vector reached(BUFSIZE);
    int unreached = 0;
    for(int i=0;i BUFSIZE)
            size = BUFSIZE;
        std::fill(reached.begin(), reached.end(), false);
        for (int j=0;j<k;j++) {
            int val = caterpillars[j];
            int first = (i % val);
            if (first != 0)
                first = val - first;
            for (int r = first; r < size; r += val)
                reached[r] = true;
        }
        for (int r = 0; r < size; r++) {
            if (!reached[r])
                unreached++;
        }
        i += size;
    }
    std::cout << unreached << 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(

StackExchange Code Review Q#143443, answer score: 3