Caterpillar Uneaten Leaves Problem – HackerEarth Interview Question

QUESTION DESCRIPTION

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 in position 0 and fall onto the leaves at positions between 1 and N. Each caterpillar i has an associated ‘jump-number’ j. A caterpillar with jump number j eats leaves at positions that are multiples of j. It will proceed in the order j, 2j, 3j, … till it reaches the end of the leaves, then it stops and builds its cocoon.

Given a set A of K elements, K ≤ 15, N ≤ 10^9, N >> K, we need to determine the number of uneaten leaves.

Input Format:
N = number of leaves
K = number of caterpillars
A = Array of integer jump numbers (one per line).

Output Format:
An integer denoting the number of uneaten leaves.

Sample Input:
10
3
2
4
5

Sample Output:
4

Explanation

[2,4,5] is the 3-member set of jump numbers. All leaves which are multiples of 2, 4, and 5 are eaten. Leaves 1,3,7,9 are left, and so the output 4.

Below is the working java code for this problem. The code seems self-explanatory, but the algorithm may be not. But for any explanation, comment below.

Note: As it is clearly mentioned that N >> K, this means the order can't be O(N). The order of my algorithm is O(2^K), which is still high but acceptable to HackerEarth.