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