Largest divisible pairs subset

Difficulty Level Medium
Frequently asked in Amazon Google
Dynamic Programming MathViews 2206

Problem Statement

The problem “Largest divisible pairs subset” states that you are given an array of n distinct elements. Find the length of largest such that each pair of the subset has the larger element divisible by smaller elements.

Example

Largest divisible pairs subset

array = {1, 2, 4, 5, 8, 9, 16}
5

Explanation

The largest subset is 1, 2, 4, 8, 16 which follows the condition specified in the problem. Since the length of this subset is 5, the answer is 5.

Approach

Let’s start with a naive approach. The simplest thing one can think of is to generate all the subsets and then check if the subset follows the given condition. If it does then store the length of the subset. Keep on updating this value with the larger subset length, if you find any that satisfies the given condition. But this approach is highly inefficient as it requires the generation of all subsets which itself requires exponential time.

So in order to efficiently solve the problem. We try to break the problem into smaller problems. The problem says all the pairs should satisfy the condition that the smaller number should divide the larger number. So, if we think about it we can think of a solution similar to that of the LIS problem. Longest Increasing Subsequence problem says to find the length of the largest subset which is in increasing order. We can do something similar using Dynamic Programming. We will first sort the array. Then for each element, we will see all the elements before it and check if any of the elements divide this current element. If any element divides the current element, we know that we can add the current element to that subset.

Thus we create a DP array whose ith element denotes the length of the largest subset which has the current element as its largest element. And the subset satisfies the condition imposed on the problem.

Code

C++ code for Largest divisible pairs subset

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

int largestDivisibleSubset(vector<int>& nums) {
    int n = nums.size();
    if(n==0)return 0;
    sort(nums.begin(), nums.end());
    int dp[n], ans = INT_MIN;
    for(int i=0;i<n;i++){
        dp[i] = 1;
        for(int j=i-1;j>=0;j--)
            if(nums[i]%nums[j] == 0){
                if((dp[j]+1)>dp[i]){
                    dp[i] = dp[j]+1;
                    ans = max(ans, dp[i]);
                }
            }
    }
    return ans;
}

int main(){
  int n;cin>>n;
  vector<int> v(n);
  for(int i=0;i<n;i++)
    cin>>v[i];
  int len = largestDivisibleSubset(v);
  cout<<len<<endl;
}

7
1 2 4 5 8 9 16
5

Java code for Largest divisible pairs subset

import java.util.*;
class Main{
  
  static int largestDivisibleSubset(ArrayList<Integer> nums) {
      int n = nums.size();
      if(n==0)return 0;
      Collections.sort(nums);
      int dp[] = new int[n];
      int ans = Integer.MIN_VALUE;
      for(int i=0;i<n;i++){
          dp[i] = 1;
          for(int j=i-1;j>=0;j--)
              if(nums.get(i)%nums.get(j) == 0){
                  if((dp[j]+1)>dp[i]){
                      dp[i] = dp[j]+1;
                      ans = Math.max(ans, dp[i]);
                  }
              }
      }
      return ans;
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> v = new ArrayList<Integer>();
    for(int i=0;i<n;i++){
      int a = sc.nextInt();
      v.add(a);
    }
    int len = largestDivisibleSubset(v);
    System.out.println(len);
  	}
}
7
1 2 4 5 8 9 16
5

Complexity Analysis

Time Complexity

O(N^2), because in the problem we traverse over all the elements which came before the current element. The time complexity is polynomial.

Space Complexity

O(N), since we have used an array for storing the values as DP table. The space complexity is linear.

Translate »