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.

	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import java.util.TreeSet;

	public class Main {

	public static void main(String[] args) {
	int[] A = { 2, 4, 5, -1, 13, 18, 0, 3, 8, 23, 27, 41, 53, 49, 13, 77, 0, 37, 83, 29 };
	System.out.println(new Main().countUneatenLeaves(Long.MAX_VALUE, A));
	}

	private long countUneatenLeaves(long numberOfLeaves, int[] jumps) {

	if (numberOfLeaves <= 0)
	return 0;

	if (jumps == null \|\| jumps.length == 0)
	return numberOfLeaves;

	jumps = getRelevantJumps(jumps);

	if (jumps[0] == 1)
	return 0;

	long eaten = 0;

	List<Integer[]> allCombinations = new ArrayList<Integer[]>();
	for (int combinationSize = 1; combinationSize <= jumps.length; combinationSize++) {
	combinationUtil(jumps, new Integer[combinationSize], 0, 0, combinationSize, allCombinations);
	}

	// System.out.println(allCombinations.size());

	for (Integer[] combination : allCombinations) {
	if (combination.length % 2 == 1) {
	eaten = eaten + numberOfLeaves / lcm(combination);
	} else {
	eaten = eaten - numberOfLeaves / lcm(combination);
	}
	}

	return numberOfLeaves - eaten;
	}

	private void combinationUtil(int arr[], Integer data[], int start, int currentCombinationIndex, int combinationSize,
	List<Integer[]> combinationList) {
	if (currentCombinationIndex == combinationSize) {
	combinationList.add(data.clone());
	return;
	}

	int length = arr.length - 1;

	for (int next = start; next <= length && length - next >= combinationSize - currentCombinationIndex - 1; next++) {
	data[currentCombinationIndex] = arr[next];
	combinationUtil(arr, data, next + 1, currentCombinationIndex + 1, combinationSize, combinationList);
	}
	}

	private long lcm(Integer[] numbers) {
	long lcm = 1;
	for (long number : numbers) {
	lcm = lcm(lcm, number);
	}
	// System.out.println("lcm of " + Arrays.toString(numbers) + " is " + lcm);
	return lcm;
	}

	private long lcm(long num1, long num2) {
	long small = Math.min(num1, num2);
	long big = Math.max(num1, num2);
	TwoNumber twoNumber = new TwoNumber(small, big);
	if (lcmMap.containsKey(twoNumber)) {
	return lcmMap.get(twoNumber);
	}
	long a = big;
	while (true) {
	if (a % small == 0) {
	lcmMap.put(twoNumber, a);
	return a;
	}
	a += big;
	}
	}

	private Map<TwoNumber, Long> lcmMap = new HashMap<>();

	class TwoNumber {
	private final long small, big;

	TwoNumber(long small, long big) {
	this.small = small;
	this.big = big;
	}

	@Override
	public int hashCode() {
	final int prime = 31;
	int result = 1;
	result = prime * result + (int) big % Integer.MAX_VALUE;
	result = prime * result + (int) small % Integer.MAX_VALUE;
	return result;
	}

	@Override
	public boolean equals(Object obj) {
	if (this == obj)
	return true;
	if (obj == null)
	return false;
	if (getClass() != obj.getClass())
	return false;
	TwoNumber other = (TwoNumber) obj;
	if (big != other.big)
	return false;
	if (small != other.small)
	return false;
	return true;
	}
	}

	private int[] getRelevantJumps(int[] jumps) {

	// jumps = IntStream.of(jumps).distinct().filter(i -> i > 0).sorted().toArray();
	// filters unique positive jumps and sorts similar to above code
	Set<Integer> jumpSet = new TreeSet<>();
	for (int jump : jumps) {
	if (jump > 0 && !jumpSet.contains(jump)) {
	jumpSet.add(jump);
	}
	}

	// removing jumps which are multiples of other jumps from a sorted list
	List<Integer> jumpFactors = new LinkedList<>();
	for (int jump : jumpSet) {
	boolean containsFactor = false;
	for (int factor : jumpFactors) {
	if (jump % factor == 0) {
	containsFactor = true;
	break;
	}
	}
	if (!containsFactor) {
	jumpFactors.add(jump);
	}
	}

	// list of integer to int array
	jumps = new int[jumpFactors.size()];
	int i = 0;
	for (Integer e : jumpFactors)
	jumps[i++] = e;

	return jumps;
	}
	}