Rabbit Jumping
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

Question

Rabbit Jumping

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

Accepted Answer

Tip 1 : Prepare Subjects in Depth for Technical Coding & Interview Round. Cracking the DE Shaw interview is not possible just by reading the short articles one night before.They ask the questions in-depth.
Tip 2 : All the Questions were basic in the HR Round !! … Be Honest in HR Round as well as Technical Rounds.
Tip 3 : Be Confident in HR Round and don't hesitate while answering and explaining situation based questions.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(n^2)Explanation:

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).

Java (SE 1.8)

/*

    Time Complexity     :   O(N ^ 2)

    Space Complexity    :   O(N)



    Where 'N' is the number of carrots.

*/



import java.util.ArrayList;



public class Solution {

    public static int remainingCarrots(int n, int k, ArrayList A) {

        boolean []visited = new boolean[n + 1];



	    for (int i = 0; i < k; i++) {

		    // Traversing the multiples of A.get(i).

		    for (int j = A.get(i); j <= n; j += A.get(i)) {

			    visited[j] = true;

		    }

	    }



	    int ans = 0;



	    // Checking for leaves which are not visited.

	    for (int i = 1; i <= n; i++) {

		    if (visited[i] == false) {

			    ans++;

		    }

	    }



	    return ans;

    }

}

Python (3.5)

"""

    Time Complexity     :   O(N ^ 2)

    Space Complexity    :   O(N)



    Where 'N' is the number of carrots.

"""



def remainingCarrots(n, k, A):



	visited = [False]*(n+1)



	for i in range(k):

		# Traversing the multiples of A[i].

		for j in range(A[i], n + 1, A[i]):

			visited[j] = True

		

	ans = 0



	# Checking for leaves which are not visited.

	for i in range(1, n + 1):

		if (visited[i] == False):

			ans += 1



	return ans

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N ^ 2)

    Space Complexity    :   O(N)



    Where 'N' is the number of carrots.

*/



int remainingCarrots(int n, int k, vector &A) {

	vector visited(n + 1, false);



	for (int i = 0; i < k; i++) {

		// Traversing the multiples of A[i].

		for (int j = A[i]; j <= n; j += A[i]) {

			visited[j] = true;

		}

	}



	int ans = 0;



	// Checking for leaves which are not visited.

	for (int i = 1; i <= n; i++) {

		if (visited[i] == false) {

			ans++;

		}

	}



	return ans;

}

Accepted Answer

Optimized Approach

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(nlogn)Explanation:

O(N * log(max(A[i]))) where ‘N’ is the number of carrots.

The worst-case occurs when the jumping factor is sorted in descending order. The inside loop takes N / A[i] steps in the worst case.

T(N) = N/A[0] + N/A[1] + ...

T(N) = N * (1/A[0] + 1/A[1] + 1/A[2] + ...)

1/A[0] + 1/A[1] + 1/A[2] + ... = log(max(A[i]) (Similar to Sieve of Eratosthenes)

T(N) = N * log(max(A[i])).