Longest Common Prime Subsequence

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in companies
AdobeNagarro SoftwareCadence Design Systems

Problem statement

Ninja got a very long summer vacation. Being very bored and tired about it, he indulges himself in solving some puzzles.

He encountered a problem in which he was given two arrays of integers of length ‘N’ and ‘M’ respectively and he had to find the longest common prime subsequence.

Ninja wants help in solving the problem as he is not getting the approach so he approaches you as he knows that you are very good at building logics. Help Ninja!

Note:

A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’, which denotes the number of test cases. Then each test case follows.

The first line of each test case contains two separated integers ‘N’ and ‘M’ denoting the length of two arrays.

The second line of each test case contains space-separated ‘N’ integers representing elements of the first array.

The third line of each test case contains space-separated ‘M’ integers representing elements of the second array.
Output format : 
For each test case print an integer representing the length of the longest prime subsequence of the two arrays.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N, M <= 5 * (10 ^ 2)
1 <= arr1[i], arr2[i] <= 300

Where arr1[i], arr2[i] represents ith element of arr1 and arr2 respectively.

Time Limit: 1 sec.
Sample Input 1 :
2
5 3
1 2 3 4 5
1 2 3
7 7
5 7 8 4 6 9 3
1 5 4 7 8 9 3
Sample Output 1 :
2
3

Explanation for Sample Test 1:

Test Case1 :
Longest prime subsequence obtained is of length 2 containing 2 and 3 from the two given arrays.

Test Case 2:
Longest prime subsequence obtained is of length 3 containing 5, 7 and 3 from the two given arrays.
Sample Input 2 :
2
6 7
5 2 1 7 8 9
1 2 3 4 5 6 7
8 4
4 7 8 5 1 2 3 6 
8 4 7 5
Sample Output 1 :
2
2
Hint

Think of the solution by first finding out the prime numbers and then searching the common prime numbers in both the arrays.

Approaches (1)
Dynamic Programming

The simplest idea is to consider all subsequences of arr1[] and check if all numbers in this subsequence are prime and appear in arr2[]. Then find the longest length of these subsequences. But the time complexity for this operation will be O(M * (2 ^ N)) where ‘M’ is the length of the first array and ‘N’ is the length of the second array.

 

We can think of an efficient solution in which first we calculate all the prime numbers from both the arrays and then find the longest common prime subsequence from them using Dynamic Programming. 

 

For Prime Numbers:

Find all the prime numbers between the minimum element of the array and the maximum element of the array using Sieve Of Eratosthenes algorithm.

 

For Longest Common Subsequence:

Store the sequence of primes from the arrays arr1[] and arr2[].

Find the LCS of the two sequences of primes.

 

Approach:

 

  • Generate all the prime numbers in the range of values of the given array using Sieve Of Eratosthenes.
  • Now make an iteration for ‘arr1’ and check the elements in ‘arr1’ which are prime and store the elements in an array, say ‘finalA’.
  • Now make an iteration for ‘arr2’ and check the elements in ‘arr2’ which are prime and store the elements in an array, say ‘finalB’.
  • Now calculate the LCS for the two arrays: ‘finalA’ and ‘finalB’ with the help of ‘lcs()’ function using Dynamic Programming.
  • Return the array after calculating the longest common subsequence.
Time Complexity

O(N * M), where ‘N’ denotes the length of the array ‘arr1’ and ‘M’ denotes the length of the array ‘arr2’.

 

Finding the longest common subsequence will cost O(N * M) time. And time complexity for calculation prime numbers using Sieve of Eratosthenes is O(N * log(N)). Therefore, time complexity in the worst case will be O(N * M).

Space Complexity

O(N * M), where ‘N’ denotes the length of the array ‘arr1’ and ‘M’ denotes the length of the array ‘arr2’.

 

As we are maintaining 2 Dimensional auxiliary space i.e. 2D array for calculating the LCS which takes maximum size of (N * M), therefore, overall space complexity will be O(N * M).

Code Solution
(100% EXP penalty)
Longest Common Prime Subsequence
Full screen
Console