Rabbit Jumping

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in companies
Expedia GroupD.E.ShawNagarro Software

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6 3
2 3 4
7 2
2 5
Sample Output 1:
2
3
Explanation For Sample Output 1:
For the first test case:
Carrots are eaten by the first rabbit: 2,4,6
Carrots are eaten by the second rabbit: 3,6
Carrots are eaten by the third rabbit: 4

Remaining Carrots: 1,5

For the second case:
Carrots are eaten by the first rabbit: 2,4,6
Carrots are eaten by the third rabbit: 5
Remaining Carrots: 1,3,7
Sample Input 2:
2
8 4
1 2 3 4
7 1
6
Sample Output 2:
0
6
Hint

Use brute force to traverse all multiples of each carrot.

Approaches (2)
Brute Force Approach

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.
Time Complexity

O(N ^ 2), Where ‘N’ is the number of carrots.

 

When the jumping factor of all rabbits is equal to 1.Then we need to traverse every carrots 'N' times. Hence, the time complexity will be O(N ^ 2).

Space Complexity

O(N), Where ‘N’ is the number of carrots.

 

The boolean visited array of size ‘N’ leads to O(N) space complexity.

Code Solution
(100% EXP penalty)
Rabbit Jumping
Full screen
Console