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 th...
Comments