The caterpillar problem (Hacker Rank Interview Questions)

The caterpillar problem.

Input:

1. int[] caterPillar = {2,4,5}
2. int totalLeaves = 10

Here, you will have fixed size array with integer elements called caterpillars.  For example: [2,4,5] and you have an integer value of totalLeaves. For example 10, so it will have values from 1 to 10.

Now the question will be like, how many leaves will be left if it will be eaten in a way where (Leaf % caterpillar == 0).

So for our example,

we have leaves [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Caterpillar 2 can eat: 2, 4, 6, 8, 10

Caterpillar 4 can eat: 4, 8

Caterpillar 5 can eat: 5, 10

So the left leaves will be: 1,3,7,9

Total of 4 leaves will be left.

Here the naïve approach would be to loop over all the leaves and also loop over all the caterpillars and discard those leaves that are divisible by it. It will have 0 (n2) complexity.

Approach 1. Here the first improvement can be achieved if you look at the caterpillar array. Here you have [2,4,5]. The easiest catch is the discard those caterpillars which are divisible by other. So which will make our caterpillar array [2,4]. It is because the leaves that are eaten by 4 can also be eaten by 2. So we do not need to loop over all the caterpillars. This way we can save many iterations by reducing unnecessary caterpillar.

Below code is an implementation of above approach.

You can have below code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

The output of above code is as below:

You can have above code from GIT.

https://github.com/Niravkumar-Patel/SnippetExampleRepo.git