Maximum length subsequence such that adjacent elements in the subsequence have a common factor

0 0 7 minutes read

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>

Output

Time Complexity: O(N* log(N))
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!