Given an array arr[], find the maximum length of a substance such that the adjacent elements in the subsequence have a common factor.

Input: arr[]={13,2,8,6,3,1,9}
Output:5

The maximum length subsequence 
with satisfied conditions: {2,8,6,3,9}
Input: arr[]={1,2,2,3,3,1}
Output:2

Consider all the subsequence and then check all the subsequence to find whether it satisfies the condition. Using the dynamic programming, let dp[i] denote the maximum length of subsequence including the arr[i].

The relation holds for all the prime p such that the p is a prime factor of arr[i].

dp[i]=max(dp[i],1+dp[pos[p]])
The pos[p] gives the index of p in the array
where it occurred last.

Transvere the array, for element arr[i] there will be two possibilities:

a) If the prime factors of arr[i] show the first appearance in the array, then dp[i]=1

b) If the prime factors of arr[i] have already occurred, then the element can be added in the subsequence. Since there is no common factor. The dp[i=max(dp[i], 1 + dp[pos[p]]) where p is the common prime factor and the pos[p] is the latest index of p in the array.

# Python function
import math as mt

N = 100005
MAX = 1000002

lpd = [0 for i in range (MAX)]

# Computing the least prime divisor of i
def preComput():
    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]=1

# Function to return the max length subsequence with the 
# adjacent elements having the common factor
 def maxLenSub(arr, n):
    dp = [1 for i in range(N+1)]

    pos = dict()

# Initializing the dp array with 1
    for i in range(1, n):
        while (arr[i]>1):
            p=lpd[arr[i]]
            if (p in pos.keys()):
    
# p will have appeared at least once
                dp[i] = max(dp[i], 1+ dp[pos[p]])

# Updating the latest occurrence of the prime p
            pos[p]=i
            while (arr[i] % p ==0):
                arr[i] //=p

# Getting the max value to be the answer
    answer = 1
    for i in range(1, n+1):
        answer = max(answer, dp[i])

    return answer

# The test code
arr = [13, 2, 8, 6, 3, 1, 9]
n = len(arr)

preComput()

print(maxLenSub(arr, n))

That’s it 🙂

If you have any question or comment, do not hesitate to ask us.

Quote: The moon looks upon many night flowers; the night flowers see but one moon. – Jean Ingelow

Advertisement