Algorithm. How to find longest subsequence of integers in an array such that gcd of any two consecutive number in the sequence is greather than 1?

Question

Given`en an array of integers. We have to find the length of the longest subsequence of integers such that gcd of any two consecutive elements in the sequence is greater than 1.

for ex: if array = [12, 8, 2, 3, 6, 9]

then one such subsequence can be = {12, 8, 2, 6, 9} other one can be= {12, 3, 6, 9}

I tried to solve this problem by dynamic programming. Assume that maxCount is the array such that maxCount[i] will have the length of such longest subsequence ending at index i.

`maxCount[0]=1 ;

for(i=1; i<N; i++)
{

   max = 1 ;

   for(j=i-1; j>=0; j--)
   {   

      if(gcd(arr[i], arr[j]) > 1)
      {
      temp = maxCount[j] + 1 ;

      if(temp > max)
       max = temp ;
     }
    }

maxCount[i]=max;

}``

max = 0;

for(i=0; i<N; i++)
{
 if(maxCount[i] > max)
   max = maxCount[i] ;
}

cout<<max<<endl ;

`

But, this approach is getting timeout. As its time complexity is O(N^2). Can we improve the time complexity?

Answer 1

GCD takes log m time, where m is the maximum number in the array. Therefore, using a Segment Tree and binary search, one can reduce the time complexity to O(n log (m² * n)) (with O(n log m) preprocessing). This list details other data structures that can be used for RMQ-type queries and to reduce the complexity further.

Here is one possible implementation of this:

#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    using ftype = function<int(int, int)>;
    vector<int> vec;
    int l, og, dummy;
    ftype f;
    template<typename T> SegTree(const vector<T> &v, const T &x, const ftype &func) : og(v.size()), f(func), l(1), dummy(x) {
        assert(og >= 1);
        while (l < og) l *= 2;
        vec = vector<int>(l*2);
        for (int i = l; i < l+og; i++) vec[i] = v[i-l];
        for (int i = l+og; i < 2*l; i++) vec[i] = dummy;
        for (int i = l-1; i >= 1; i--) {
            if (vec[2*i] == dummy && vec[2*i+1] == dummy) vec[i] = dummy;
            else if (vec[2*i] == dummy) vec[i] = vec[2*i+1];
            else if (vec[2*i+1] == dummy) vec[i] = vec[2*i];
            else vec[i] = f(vec[2*i], vec[2*i+1]);
        }
    }
    SegTree() {}
    void valid(int x) {assert(x >= 0 && x < og);}
    int get(int a, int b) {
        valid(a); valid(b); assert(b >= a);
        a += l; b += l;
        int s = vec[a];
        a++;
        while (a <= b) {
            if (a % 2 == 1) {
                if (vec[a] != dummy) s = f(s, vec[a]);
                a++;
            }
            if (b % 2 == 0) {
                if (vec[b] != dummy) s = f(s, vec[b]);
                b--;
            }
            a /= 2; b /= 2;
        }
        return s;
    }
    void add(int x, int c) {
        valid(x);
        x += l;
        vec[x] += c;
        for (x /= 2; x >= 1; x /= 2) {
            if (vec[2*x] == dummy && vec[2*x+1] == dummy) vec[x] = dummy;
            else if (vec[2*x] == dummy) vec[x] = vec[2*x+1];
            else if (vec[2*x+1] == dummy) vec[x] = vec[2*x];
            else vec[x] = f(vec[2*x], vec[2*x+1]);
        }
    }
    void update(int x, int c) {add(x, c-vec[x+l]);}
};
// Constructor (where val is something that an element in the array is
// guaranteed to never reach):
// SegTree st(vec, val, func);

// finds longest subsequence where GCD is greater than 1
int longest(const vector<int> &vec) {
    int l = vec.size();
    SegTree st(vec, -1, [](int a, int b){return __gcd(a, b);});
    
    // checks if a certain length is valid in O(n log (m² * n)) time
    auto valid = [&](int n) -> bool {
        for (int i = 0; i <= l-n; i++) {
            if (st.get(i, i+n-1) != 1) {
                return true;
            }
        }
        return false;
    };
    
    int length = 0;
    // do a "binary search" on the best possible length
    for (int i = l; i >= 1; i /= 2) {
        while (length+i <= l && valid(length+i)) {
            length += i;
        }
    }
    return length;
}

Answer 2

The condition "gcd is greater than 1" means that numbers have at least one common divisor. So, let dp[i] equals to the length of longest sequence finishing on a number divisible by i.

int n;
cin >> n;

const int MAX_NUM = 100 * 1000;
static int dp[MAX_NUM];

for(int i = 0; i < n; ++i)
{
    int x;
    cin >> x;

    int cur = 1;
    vector<int> d;
    for(int i = 2; i * i <= x; ++i)
    {
        if(x % i == 0)
        {
            cur = max(cur, dp[i] + 1);
            cur = max(cur, dp[x / i] + 1);
            d.push_back(i);
            d.push_back(x / i);
        }
    }
    if(x > 1)
    {
        cur = max(cur, dp[x] + 1);
        d.push_back(x);
    }

    for(int j : d)
    {
        dp[j] = cur;
    }
}

cout << *max_element(dp, dp + MAX_NUM) << endl;

This solution has O(N * sqrt(MAX_NUM)) complexity. Actually you can calculate dp values only for prime numbers. To implement this you should be able to get prime factorization in less than O(N^0.5) time (this method, for example). That optimization should cast complexity to O(N * factorization + Nlog(N)). As memory optimization, you can replace dp array with map or unordered_map.