Maximum length subsequence such that adjacent elements in the subsequence have a common factor
Given an array arr[], the task is to find the maximum length of a subsequence such that the adjacent elements in the subsequence have a common factor.
Examples:
Input: arr[] = { 13, 2, 8, 6, 3, 1, 9 }
Output: 5
Max length subsequence with satisfied conditions: { 2, 8, 6, 3, 9 }Input: arr[] = { 12, 2, 8, 6, 3, 1, 9 }
Output: 6
Max length subsequence with satisfied conditions: {12, 2, 8, 6, 3, 9 }Input: arr[] = { 1, 2, 2, 3, 3, 1 }
Output: 2
Approach: A naive approach is to consider all subsequences and check every subsequence whether it satisfies the condition.
An efficient solution is to use Dynamic programming. Let dp[i] denote the maximum length of subsequence including arr[i]. Then, the following relation holds for every prime p such that p is a prime factor of arr[i]:
dp[i] = max(dp[i], 1 + dp[pos[p]]) where pos[p] gives the index of p in the array where it last occurred.
Explanation: Traverse the array. For an element arr[i], there are 2 possibilities.
- If the prime factors of arr[i] have shown their first appearance in the array, then dp[i] = 1
- If the prime factors of arr[i] have already occurred, then this element can be added in the subsequence since there’s a common factor. Hence dp[i] = max(dp[i], 1 + dp[pos[p]]) where p is the common prime factor and pos[p] is the latest index of p in the array.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> #define N 100005 #define MAX 10000002 using namespace std; int lpd[MAX]; // Function to compute least // prime divisor of i void preCompute() { memset (lpd, 0, sizeof (lpd)); lpd[0] = lpd[1] = 1; for ( int i = 2; i * i < MAX; i++) { for ( int j = i * 2; j < MAX; j += i) { if (lpd[j] == 0) { lpd[j] = i; } } } for ( int i = 2; i < MAX; i++) { if (lpd[i] == 0) { lpd[i] = i; } } } // Function that returns the maximum // length subsequence such that // adjacent elements have a common factor. int maxLengthSubsequence( int arr[], int n) { int dp[N]; unordered_map< int , int > pos; // Initialize dp array with 1. for ( int i = 0; i <= n; i++) dp[i] = 1; for ( int i = 0; i <= n; i++) { while (arr[i] > 1) { int p = lpd[arr[i]]; if (pos[p]) { // p has appeared at least once. dp[i] = max(dp[i], 1 + dp[pos[p]]); } // Update latest occurrence of prime p. pos[p] = i; while (arr[i] % p == 0) arr[i] /= p; } } // Take maximum value as the answer. int ans = 1; for ( int i = 0; i <= n; i++) { ans = max(ans, dp[i]); } return ans; } // Driver code int main() { int arr[] = { 13, 2, 8, 6, 3, 1, 9 }; int n = sizeof (arr) / sizeof (arr[0]); preCompute(); cout << maxLengthSubsequence(arr, n); return 0; } |
Python3
# Python3 implementation of the # above approach import math as mt N = 100005 MAX = 1000002 lpd = [ 0 for i in range ( MAX )] # to compute least prime divisor of i def preCompute(): lpd[ 0 ], lpd[ 1 ] = 1 , 1 for i in range ( 2 , mt.ceil(mt.sqrt( MAX ))): for j in range ( 2 * i, MAX , i): if (lpd[j] = = 0 ): lpd[j] = i for i in range ( 2 , MAX ): if (lpd[i] = = 0 ): lpd[i] = i # Function that returns the maximum # length subsequence such that # adjacent elements have a common factor. def maxLengthSubsequence(arr, n): dp = [ 1 for i in range (N + 1 )] pos = dict () # Initialize dp array with 1. for i in range ( 0 , n): while (arr[i] > 1 ): p = lpd[arr[i]] if (p in pos.keys()): # p has appeared at least once. dp[i] = max (dp[i], 1 + dp[pos[p]]) # Update latest occurrence of prime p. pos[p] = i while (arr[i] % p = = 0 ): arr[i] / / = p # Take maximum value as the answer. ans = 1 for i in range ( 0 , n + 1 ): ans = max (ans, dp[i]) return ans # Driver code arr = [ 13 , 2 , 8 , 6 , 3 , 1 , 9 ] n = len (arr) preCompute() print (maxLengthSubsequence(arr, n)) # This code is contributed by Mohit Kumar |
Java
// Java implementation of the above approach import java.util.*; class GfG { static int N, MAX; // Check if UpperBound is // given for all test Cases // N = 100005 ; // MAX = 10000002; static int lpd[]; // Function to compute least prime divisor // of i upto MAX element of the input array // it will be space efficient // if more test cases are there it's // better to find prime divisor // upto upperbound of input element // it will be cost efficient static void preCompute() { lpd = new int [MAX + 1 ]; lpd[ 0 ] = lpd[ 1 ] = 1 ; for ( int i = 2 ; i * i <= MAX; i++) { for ( int j = i * 2 ; j <= MAX; j += i) { if (lpd[j] == 0 ) { lpd[j] = i; } } } for ( int i = 2 ; i <= MAX; i++) { if (lpd[i] == 0 ) { lpd[i] = i; } } } // Function that returns the maximum // length subsequence such that // adjacent elements have a common factor. static int maxLengthSubsequence(Integer arr[], int n) { Integer dp[] = new Integer[N]; Map<Integer, Integer> pos = new HashMap<Integer, Integer>(); // Initialize dp array with 1. for ( int i = 0 ; i <= n; i++) dp[i] = 1 ; for ( int i = 0 ; i <= n; i++) { while (arr[i] > 1 ) { int p = lpd[arr[i]]; if (pos.containsKey(p)) { // p has appeared at least once. dp[i] = Math.max(dp[i], 1 + dp[pos.get(p)]); } // Update latest occurrence of prime p. pos.put(p, i); while (arr[i] % p == 0 ) arr[i] /= p; } } // Take maximum value as the answer. int ans = Collections.max(Arrays.asList(dp)); return ans; } // Driver code public static void main(String[] args) { Integer arr[] = { 12 , 2 , 8 , 6 , 3 , 1 , 9 }; N = arr.length; MAX = Collections.max(Arrays.asList(arr)); preCompute(); System.out.println( maxLengthSubsequence(arr, N - 1 )); } } // This code is contributed by Prerna Saini. |
C#
// C# implementation of the // above approach using System; using System.Collections; class GFG { static int N = 100005; static int MAX = 10000002; static int [] lpd = new int [MAX]; // to compute least prime divisor of i static void preCompute() { lpd[0] = lpd[1] = 1; for ( int i = 2; i * i < MAX; i++) { for ( int j = i * 2; j < MAX; j += i) { if (lpd[j] == 0) { lpd[j] = i; } } } for ( int i = 2; i < MAX; i++) { if (lpd[i] == 0) { lpd[i] = i; } } } // Function that returns the maximum // length subsequence such that // adjacent elements have a common factor. static int maxLengthSubsequence( int [] arr, int n) { int [] dp = new int [N]; Hashtable pos = new Hashtable(); // Initialize dp array with 1. for ( int i = 0; i <= n; i++) dp[i] = 1; for ( int i = 0; i <= n; i++) { while (arr[i] > 1) { int p = lpd[arr[i]]; if (pos.ContainsKey(p)) { // p has appeared at least once. dp[i] = Math.Max( dp[i], 1 + dp[Convert.ToInt32(pos[p])]); } // Update latest occurrence of prime p. pos[p] = i; while (arr[i] % p == 0) arr[i] /= p; } } // Take maximum value as the answer. int ans = 1; for ( int i = 0; i <= n; i++) { ans = Math.Max(ans, dp[i]); } return ans; } // Driver code public static void Main() { int [] arr = { 13, 2, 8, 6, 3, 1, 9 }; int n = arr.Length - 1; preCompute(); Console.WriteLine(maxLengthSubsequence(arr, n)); } } // This code is contributed by Ryuga |
Javascript
<script> // JavaScript implementation of the above approach let N, MAX; // Check if UpperBound is // given for all test Cases // N = 100005 ; // MAX = 10000002; let lpd; // Function to compute least prime divisor // of i upto MAX element of the input array // it will be space efficient // if more test cases are there it's // better to find prime divisor // upto upperbound of input element // it will be cost efficient function preCompute() { lpd = new Array(MAX + 1); for (let i=0;i<lpd.length;i++) { lpd[i]=0; } lpd[0] = lpd[1] = 1; for (let i = 2; i * i <= MAX; i++) { for (let j = i * 2; j <= MAX; j += i) { if (lpd[j] == 0) { lpd[j] = i; } } } for (let i = 2; i <= MAX; i++) { if (lpd[i] == 0) { lpd[i] = i; } } } // Function that returns the maximum // length subsequence such that // adjacent elements have a common factor. function maxLengthSubsequence(arr,n) { let dp = new Array(N); let pos = new Map(); // Initialize dp array with 1. for (let i = 0; i <= n; i++) dp[i] = 1; for (let i = 0; i <= n; i++) { while (arr[i] > 1) { let p = lpd[arr[i]]; if (pos.has(p)) { // p has appeared at least once. dp[i] = Math.max(dp[i], 1 + dp[pos.get(p)]); } // Update latest occurrence of prime p. pos.set(p, i); while (arr[i] % p == 0) arr[i] = Math.floor(arr[i]/p); } } // Take maximum value as the answer. let ans = Math.max(...dp); return ans; } // Driver code let arr=[13, 2, 8, 6, 3, 1, 9 ]; N = arr.length; MAX = Math.max(...arr); preCompute(); document.write(maxLengthSubsequence(arr, N - 1)); // This code is contributed by patel2127 </script> |
5
Time Complexity: O(N* log(N))
Auxiliary Space: O(N)