Given two arrays arr1[] and arr2[] of length N and M respectively, the task is to find the length of the longest common prime subsequence that can be obtained from the two given arrays.
Examples:
Input: arr1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, arr2[] = {2, 5, 6, 3, 7, 9, 8}
Output: 4
Explanation:
The longest common prime subsequence present in both the arrays is {2, 3, 5, 7}.Input: arr1[] = {1, 3, 5, 7, 9}, arr2[] = {2, 4, 6, 8, 10}
Output: 0
Explanation:
In the above arrays, the prime subsequence of arr1[] is {1, 3, 5, 7} and arr2[] is {2}. Therefore, there is no common prime numbers which are present in both the arrays. Hence, the result is 0.
Naive Approach: 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.
Time Complexity: O(M * 2N)
Auxiliary Space: O(N)
Efficient Approach: The idea is to find all the prime numbers from both the arrays and then find the longest common prime subsequence from them using Dynamic Programming. Follow the steps below to solve the problem:
- Find all the prime numbers between the minimum element of the array and maximum element of the array using Sieve Of Eratosthenes algorithm.
- Store the sequence of primes from the arrays arr1[] and arr2[].
- Find the LCS of the two sequences of primes.
Below is the implementation of the above approach:
C++
// CPP implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the LCSint recursion(vector<int> arr1, vector<int> arr2, int i, int j, map<pair<int, int>, int> dp){ if (i >= arr1.size() or j >= arr2.size()) return 0; pair<int, int> key = { i, j }; if (arr1[i] == arr2[j]) return 1 + recursion(arr1, arr2, i + 1, j + 1, dp); if (dp.find(key) != dp.end()) return dp[key]; else dp[key] = max(recursion(arr1, arr2, i + 1, j, dp), recursion(arr1, arr2, i, j + 1, dp)); return dp[key];}// Function to generate// all the possible// prime numbersvector<int> primegenerator(int n){ int cnt = 0; vector<int> primes(n + 1, true); int p = 2; while (p * p <= n) { for (int i = p * p; i <= n; i += p) primes[i] = false; p += 1; } return primes;}// Function which returns the// length of longest common// prime subsequenceint longestCommonSubseq(vector<int> arr1, vector<int> arr2){ // Minimum element of // both arrays int min1 = *min_element(arr1.begin(), arr1.end()); int min2 = *min_element(arr2.begin(), arr2.end()); // Maximum element of // both arrays int max1 = *max_element(arr1.begin(), arr1.end()); int max2 = *max_element(arr2.begin(), arr2.end()); // Generating all primes within // the max range of arr1 vector<int> a = primegenerator(max1); // Generating all primes within // the max range of arr2 vector<int> b = primegenerator(max2); vector<int> finala; vector<int> finalb; // Store precomputed values map<pair<int, int>, int> dp; // Store all primes in arr1[] for (int i = min1; i <= max1; i++) { if (find(arr1.begin(), arr1.end(), i) != arr1.end() and a[i] == true) finala.push_back(i); } // Store all primes of arr2[] for (int i = min2; i <= max2; i++) { if (find(arr2.begin(), arr2.end(), i) != arr2.end() and b[i] == true) finalb.push_back(i); } // Calculating the LCS return recursion(finala, finalb, 0, 0, dp);}// Driver Codeint main(){ vector<int> arr1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; vector<int> arr2 = { 2, 5, 6, 3, 7, 9, 8 }; // Function Call cout << longestCommonSubseq(arr1, arr2);} |
Java
// JAVA implementation of the above approachimport java.util.*;import java.io.*;import java.math.*;public class GFG{ // Function to calculate the LCS static int recursion(ArrayList<Integer> arr1, ArrayList<Integer> arr2, int i, int j, Map<ArrayList<Integer>, Integer> dp) { if (i >= arr1.size() || j >= arr2.size()) return 0; ArrayList<Integer> key = new ArrayList<>(); key.add(i); key.add(j); if (arr1.get(i) == arr2.get(j)) return 1 + recursion(arr1, arr2, i + 1, j + 1, dp); if (dp.get(key) != dp.get(dp.size()-1)) return dp.get(key); else dp.put(key,Math.max(recursion(arr1, arr2, i + 1, j, dp), recursion(arr1, arr2, i, j + 1, dp))); return dp.get(key); } // Function to generate // all the possible // prime numbers static ArrayList<Boolean> primegenerator(int n) { int cnt = 0; ArrayList<Boolean> primes = new ArrayList<>(); for(int i = 0; i < n + 1; i++) primes.add(true); int p = 2; while (p * p <= n) { for (int i = p * p; i <= n; i += p) primes.set(i,false); p += 1; } return primes; } // Function that returns the Minimum element of an ArrayList static int min_element(ArrayList<Integer> al) { int min = Integer.MAX_VALUE; for(int i = 0; i < al.size(); i++) { min=Math.min(min, al.get(i)); } return min; } // Function that returns the Minimum element of an ArrayList static int max_element(ArrayList<Integer> al) { int max = Integer.MIN_VALUE; for(int i = 0; i < al.size(); i++) { max = Math.max(max, al.get(i)); } return max; } // Function which returns the // length of longest common // prime subsequence static int longestCommonSubseq(ArrayList<Integer> arr1, ArrayList<Integer> arr2) { // Minimum element of // both arrays int min1 = min_element(arr1); int min2 = min_element(arr2); // Maximum element of // both arrays int max1 = max_element(arr1); int max2 = max_element(arr2); // Generating all primes within // the max range of arr1 ArrayList<Boolean> a = primegenerator(max1); // Generating all primes within // the max range of arr2 ArrayList<Boolean> b = primegenerator(max2); ArrayList<Integer> finala = new ArrayList<>(); ArrayList<Integer> finalb = new ArrayList<>(); // Store precomputed values Map<ArrayList<Integer>,Integer> dp = new HashMap <ArrayList<Integer>,Integer> (); // Store all primes in arr1[] for (int i = min1; i <= max1; i++) { if (arr1.contains(i) && a.get(i) == true) finala.add(i); } // Store all primes of arr2[] for (int i = min2; i <= max2; i++) { if (arr2.contains(i) && b.get(i) == true) finalb.add(i); } // Calculating the LCS return recursion(finala, finalb, 0, 0, dp); } // Driver Code public static void main(String args[]) { int a1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int a2[] = { 2, 5, 6, 3, 7, 9, 8 }; // Converting into list ArrayList<Integer> arr1 = new ArrayList<Integer>(); for(int i = 0; i < a1.length; i++) arr1.add(a1[i]); ArrayList<Integer> arr2 = new ArrayList<Integer>(); for(int i = 0; i < a2.length; i++) arr2.add(a2[i]); // Function Call System.out.println(longestCommonSubseq(arr1, arr2)); }}// This code is contributed by jyoti369 |
Python3
# Python implementation of the above approach# Function to calculate the LCSdef recursion(arr1, arr2, i, j, dp): if i >= len(arr1) or j >= len(arr2): return 0 key = (i, j) if arr1[i] == arr2[j]: return 1 + recursion(arr1, arr2, i + 1, j + 1, dp) if key in dp: return dp[key] else: dp[key] = max(recursion(arr1, arr2, i + 1, j, dp), recursion(arr1, arr2, i, j + 1, dp)) return dp[key]# Function to generate# all the possible# prime numbersdef primegenerator(n): cnt = 0 primes = [True for _ in range(n + 1)] p = 2 while p * p <= n: for i in range(p * p, n + 1, p): primes[i] = False p += 1 return primes# Function which returns the# length of longest common# prime subsequencedef longestCommonSubseq(arr1, arr2): # Minimum element of # both arrays min1 = min(arr1) min2 = min(arr2) # Maximum element of # both arrays max1 = max(arr1) max2 = max(arr2) # Generating all primes within # the max range of arr1 a = primegenerator(max1) # Generating all primes within # the max range of arr2 b = primegenerator(max2) finala = [] finalb = [] # Store precomputed values dp = dict() # Store all primes in arr1[] for i in range(min1, max1 + 1): if i in arr1 and a[i] == True: finala.append(i) # Store all primes of arr2[] for i in range(min2, max2 + 1): if i in arr2 and b[i] == True: finalb.append(i) # Calculating the LCS return recursion(finala, finalb, 0, 0, dp)# Driver Codearr1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]arr2 = [2, 5, 6, 3, 7, 9, 8]# Function Callprint(longestCommonSubseq(arr1, arr2)) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;using System.Linq;using System.Text;namespace GFG { class Program { // Function to calculate the LCS static int recursion(List<int> arr1, List<int> arr2, int i, int j, Dictionary<List<int>, int> dp) { if (i >= arr1.Count || j >= arr2.Count) return 0; List<int> key = new List<int>(); key.Add(i); key.Add(j); if (arr1[i] == arr2[j]) return 1 + recursion(arr1, arr2, i + 1, j + 1, dp); if (dp.ContainsKey(key)) return dp[key]; else dp[key] = Math.Max( recursion(arr1, arr2, i + 1, j, dp), recursion(arr1, arr2, i, j + 1, dp)); return dp[key]; } // Function to generate // all the possible // prime numbers static List<bool> primegenerator(int n) { int cnt = 0; List<bool> primes = new List<bool>(); for (int i = 0; i < n + 1; i++) primes.Add(true); int p = 2; while (p * p <= n) { for (int i = p * p; i <= n; i += p) primes[i] = false; p += 1; } return primes; } // Function that returns the Minimum element of an List static int min_element(List<int> al) { int min = int.MaxValue; for (int i = 0; i < al.Count; i++) { min = Math.Min(min, al[i]); } return min; } // Function that returns the Minimum element of an List static int max_element(List<int> al) { int max = int.MinValue; for (int i = 0; i < al.Count; i++) { max = Math.Max(max, al[i]); } return max; } // Function which returns the // length of longest common // prime subsequence static int longestCommonSubseq(List<int> arr1, List<int> arr2) { // Minimum element of // both arrays int min1 = min_element(arr1); int min2 = min_element(arr2); // Maximum element of // both arrays int max1 = max_element(arr1); int max2 = max_element(arr2); // Generating all primes within // the max range of arr1 List<bool> a = primegenerator(max1); // Generating all primes within // the max range of arr2 List<bool> b = primegenerator(max2); List<int> finala = new List<int>(); List<int> finalb = new List<int>(); // Store precomputed values Dictionary<List<int>, int> dp = new Dictionary<List<int>, int>(); // Store all primes in arr1[] for (int i = min1; i <= max1; i++) { if (arr1.Contains(i) && a[i] == true) finala.Add(i); } // Store all primes of arr2[] for (int i = min2; i <= max2; i++) { if (arr2.Contains(i) && b[i] == true) finalb.Add(i); } // Return the length of LCS return recursion(finala, finalb, 0, 0, dp); } static void Main(string[] args) { List<int> arr1 = new List<int>{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }; List<int> arr2 = new List<int>{2, 5, 6, 3, 7, 9, 8 }; Console.WriteLine(longestCommonSubseq(arr1, arr2)); Console.ReadLine(); } }}// This code is contributed by lokeshpotta20. |
Javascript
// JavaScript implementation of the above approachconst longestCommonSubseq = (arr1, arr2) => { const recursion = (arr1, arr2, i, j, dp) => { if (i >= arr1.length || j >= arr2.length) return 0; const key = i + ',' + j; if (arr1[i] === arr2[j]) return 1 + recursion(arr1, arr2, i + 1, j + 1, dp); if (dp[key] !== undefined) return dp[key]; else { dp[key] = Math.max(recursion(arr1, arr2, i + 1, j, dp), recursion(arr1, arr2, i, j + 1, dp)); return dp[key]; } }; const primegenerator = n => { let primes = Array(n + 1).fill(true); let p = 2; while (p * p <= n) { for (let i = p * p; i <= n; i += p) primes[i] = false; p++; } return primes; }; const min1 = Math.min(...arr1); const min2 = Math.min(...arr2); const max1 = Math.max(...arr1); const max2 = Math.max(...arr2); const a = primegenerator(max1); const b = primegenerator(max2); let finala = []; let finalb = []; const dp = {}; for (let i = min1; i <= max1; i++) { if (arr1.includes(i) && a[i]) finala.push(i); } for (let i = min2; i <= max2; i++) { if (arr2.includes(i) && b[i]) finalb.push(i); } return recursion(finala, finalb, 0, 0, dp);};console.log(longestCommonSubseq([1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 5, 6, 3, 7, 9, 8])); |
Output
4
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
