Last Updated: 16 Mar, 2021
Rabbit Jumping
Easy
Asked in companies
You are given ‘n’ carrots numbered from 1 to ‘n’. There are k rabbits. Rabbits can jump to carrots only with the multiples of Aj(Aj,2Aj,3Aj…) for all rabbits from 1 to k.
Whenever Rabbit reaches a carrot it eats a little carrot. All rabbits start from the same beginning point. You have to determine the remaining carrots(i.e., carrots which are not eaten by any rabbit) after all rabbits reach the end.
Input Format:
The first line of input contains an integer 'T' denoting the number of test cases.
The first line of the test case contains 'n' and 'k' denoting the number of carrots and rabbits.
The next line contains 'k' space-separated integers denoting the jumping factor of the rabbits.
Output Format:
Return a single integer representing the number of remaining carrots.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= 'T' <= 50
1 <= 'n', 'k' <= 3000
1 <= A[ j ] <= n, for all j from 1 to k
Time Limit: 1 second
Approaches
Explanation:
The main idea is to traverse all multiples of A[j] for all j from 1 to k. After traversing the total number of left carrots will be the answer.
Algorithm :
- Create a boolean array of size ‘n + 1’ with default value false.
- Run a loop from i = 0 to k, Traverse all multiples of 'A[i]' less than 'n'. The carrots which are visited mark it true.
- After doing traversal count the values from 1 to n with false values. Return this value.
Explanation:
The main idea is to traverse all multiples of A[j] for all j from 1 to k. If a particular A[j] have been traversed then we don’t need to traverse its multiples(When A[j] have been traversed it means it has been multiple of some jumping factor of any rabbit. Hence all the multiples of A[j] have been the multiples of the same jumping factor of rabbit).
Algorithm:
- Create a boolean array of size n + 1 with default value false.
- Run a loop from i=0 to k. If A[i] is marked true then we don’t need to traverse its multiples as they have been already traversed. Else Traverse all multiples of A[i] less than n. The carrots which are visited mark it true.
- After doing traversal count the values from 1 to n with false values. Return this value.