Last Updated: 25 Jun, 2021
Longest Common Prime Subsequence
Moderate
Asked in companies
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.
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.
Approaches
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.