सर्वात मोठा विभागणीयोग्य जोड्या सबसेट


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन Google
डायनॅमिक प्रोग्रामिंग गणित

समस्या विधान

“सर्वात मोठे विभाज्य जोड्या सबसेट” या समस्येमध्ये असे म्हटले आहे की आपणास n भिन्न घटकांचा अ‍ॅरे देण्यात आला आहे. सर्वात मोठी लांबी शोधा जे सबसेटच्या प्रत्येक जोडीला लहान घटकांद्वारे विभाजित करण्यायोग्य मोठा घटक असतो.

उदाहरण

सर्वात मोठा विभागणीयोग्य जोड्या सबसेट

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

स्पष्टीकरण

सर्वात मोठा उपसंच 1, 2, 4, 8, 16 आहे जो समस्येमध्ये निर्दिष्ट केलेल्या अटचे पालन करतो. या उपसेटची लांबी 5 असल्याने उत्तर 5 आहे.

दृष्टीकोन

चला एक निष्कपट दृष्टिकोन सह प्रारंभ करूया. सर्वात सोपी गोष्ट जी आपण विचार करू शकतो ती सर्व उपनिर्मिती करणे आणि नंतर सबसेट दिलेल्या शर्तीचे अनुसरण करीत आहे की नाही ते तपासा. जर असे नसेल तर उपसेटची लांबी संचयित करा. आपणास दिलेली अट पूर्ण करणारे कोणतेही आढळल्यास, हे मूल्य मोठ्या सबसेट लांबीसह अद्यतनित करणे सुरू ठेवा. परंतु हा दृष्टिकोन अत्यंत अकार्यक्षम आहे कारण त्यासाठी सर्व उपनिर्मिती तयार करणे आवश्यक आहे ज्यास स्वतःच घातांक वेळ आवश्यक आहे.

म्हणून कार्यक्षमतेने समस्येचे निराकरण करण्यासाठी. आम्ही समस्या लहान समस्यांमधे मोडण्याचा प्रयत्न करतो. समस्या म्हणते की सर्व जोड्यांनी ही अट पूर्ण केली पाहिजे की लहान संख्येने मोठ्या संख्येने विभाजित केले जावे. म्हणून, जर आपण त्याबद्दल विचार केला तर आम्ही एलआयएस समस्येच्या समाधानाबद्दल विचार करू शकतो. दीर्घकाळ वाढणारा उपक्रम वाढत्या क्रमाने असलेल्या सर्वात मोठ्या सबसेटची लांबी शोधण्यासाठी समस्या म्हणतात. आपण असे काहीतरी करून वापरु शकतो डायनॅमिक प्रोग्रामिंग. प्रथम अ‍ॅरे सॉर्ट करू. नंतर प्रत्येक घटकासाठी आम्ही त्या अगोदरचे सर्व घटक पाहू आणि घटकांपैकी कुठल्याहीने या विद्यमान घटकाचे विभाजन केले की नाही ते तपासू. कोणतीही घटक विद्यमान घटकास विभाजित करत असल्यास, आम्हाला माहित आहे की आम्ही त्या उपसमूहात वर्तमान घटक जोडू शकतो.

अशाप्रकारे आम्ही एक डीपी अ‍ॅरे तयार करतो ज्याचा आयथ एलिमेंट सर्वात मोठा उपसेटची लांबी दर्शवितो ज्यामध्ये सध्याचा घटक सर्वात मोठा घटक आहे. आणि उपसेट समस्येवर लागू केलेल्या अट पूर्ण करते.

कोड

सर्वात मोठ्या विभाजनीय जोड्या सबसेटसाठी सी ++ कोड

#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

सर्वात मोठ्या विभाजनीय जोड्या सबसेटसाठी जावा कोड

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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन ^ 2), कारण समस्येमध्ये आम्ही वर्तमान घटकांपूर्वी आलेल्या सर्व घटकांवर नजर ठेवतो. वेळ गुंतागुंत बहुवचन आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), डीपी टेबल म्हणून व्हॅल्यूज संचित करण्यासाठी आपण अ‍ॅरेचा वापर केला आहे. जागेची जटिलता रेखीय आहे.