मीटर द्वारे विभाजनीय योग्यासह सबसेट


अडचण पातळी हार्ड
वारंवार विचारले आर्सेसियम सिस्को डीई शॉ डायरेक्टि यामध्ये Myntra पीएयू
अरे डायनॅमिक प्रोग्रामिंग

समस्या विधान

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

उदाहरण

मीटर द्वारे विभाजनीय योग्यासह सबसेट

array = {1, 2, 4}
m = 3
True

स्पष्टीकरण

सबसेट ज्याचे मूल्य म्हणून {1,2} बेरीज 3 असतात. , 2, 4} देखील 6 देण्यास बेरीज करते जे 3 ने देखील विभाजनीय आहे. अशा प्रकारे उत्तर खरे आहे.

दृष्टीकोन

तर, आपण देखील अशीच समस्या पार पाडली आहे जी आता हे तपासून पहा उपसमटाची बेरीज योगाच्या योगे इतकी असते. परंतु येथे उपसेट-बेरीज दिलेल्या रकमेच्या समान आहे की नाही हे तपासू नका परंतु आम्ही उपसमय-योग मीटरने विभाजनीय आहे की नाही हे तपासण्याची आवश्यकता आहे. म्हणून आम्ही समस्या पुन्हा सांगू शकतो कारण जर उपसेटमध्ये दिलेल्या मूल्यांपेक्षा समान रक्कम असेल तर बेरीज = मी, 2 मी, 3 मी, .. इत्यादी उपसेट आहे किंवा नाही हे शोधणे आवश्यक आहे. आम्ही खोट्या दुसर्‍यास परत करतो.

तर, अशाप्रकारे विचार करण्याऐवजी. आम्ही बेरीजची मोड घेत आहोत आणि जर आम्हाला काही प्रमाणात ० मिळाले तर आम्हाला खात्री आहे की मीटरने विभाजनीय एक उपसमूह अस्तित्त्वात आहे. परंतु त्यापूर्वी आपण एखाद्या गोष्टीची काळजी घेणे आवश्यक आहे. घटकांची संख्या असल्यास एन> = मी (ज्यांच्या मोडची नोंद घेतली पाहिजे त्या विरुद्ध). मग उत्तर नेहमीच पिजनहोल तत्त्वामुळे अस्तित्त्वात असते. आम्हाला केवळ 0 ते मीटर -0 असणार्‍या प्रकरणांचा सामना करण्याची आवश्यकता आहे जी एन <= मी आहे.

तर, या पध्दतीमागील संपूर्ण कल्पना अशी आहे की आपल्याकडे बेरीज = j असलेले काही उपसमूह आहेत, तर आपण बेरीज = (j + करंट_इलेमेंट)% मीटर असलेले नवीन सबसेट तयार करू. आणि अशाप्रकारे आपण आपले भरणार आहोत डायनॅमिक प्रोग्रामिंग टेबल

कोड

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

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

bool findSubsetDivisibleByM(int arr[], int n, int m)
{
  // because of piegonhole principle
  if (n > m)
    return true;

  // this will work as dp array for all elements until the last element
  bool dp[m]; memset(dp, false, m);

  for (int i=0; i<n; i++)
  {
    // this will work as our current dp array
    bool tmp[m]; memset(tmp,false,m);

    // we will add the current element to all possible subset sum
    // until now and then take the mod of the sum and will keep
    // on filling the current dp array(tmp)
    for (int j=0; j<m; j++)
    {
      // if the dp table until the last element has subset sum = j
      if (dp[j] == true)
      {
        if (dp[(j+arr[i]) % m] == false)
          // fill the current dp table(tmp array)
          tmp[(j+arr[i]) % m] = true;
      }
    }

    // now just fill the original dp array
    for (int j=0; j<m; j++)
      if (tmp[j] == true)
        dp[j] = true;
    // fill the dp array considering you have subset made of only current element
    dp[arr[i]%m] = true;
  }

  return dp[0];
}

int main(){
  // Number of elements
  int n;cin>>n;
  // Number which should divide the subset
  int m;cin>>m;
  // array to store non-negative numbers
  int a[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  bool can = findSubsetDivisibleByM(a, n, m);
  if(can == true)
    cout<<"There exists a subset having sum divisible by m";
  else
    cout<<"There does not exist any subset having sum divisible by m";
}
3 3 
1 2 4
There exists a subset having sum divisible by m

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

import java.util.*;
class Main{
  
  	static boolean findSubsetDivisibleByM(int arr[], int n, int m)
  {
    // because of piegonhole principle
    if (n > m)
      return true;

    // this will work as dp array for all elements until the last element
    boolean dp[] = new boolean [m];
    for(int i=0;i<m;i++)
      dp[i] = false;

    for (int i=0;i<n; i++)
    {
      // this will work as our current dp array
      boolean tmp[] = new boolean[m];
      for(int j=0;j<m;j++)
        tmp[j] = false;
      // we will add the current element to all possible subset sum
      // until now and then take the mod of the sum and will keep
      // on filling the current dp array(tmp)
      for (int j=0; j<m; j++)
      {
        // if the dp table until the last element has subset sum = j
        if (dp[j] == true)
        {
          if (dp[(j+arr[i]) % m] == false)
            // fill the current dp table(tmp array)
            tmp[(j+arr[i]) % m] = true;
        }
      }

      // now just fill the original dp array
      for (int j=0; j<m; j++)
        if (tmp[j] == true)
          dp[j] = true;
      // fill the dp array considering you have subset made of only current element
      dp[arr[i]%m] = true;
    }

    return dp[0];
  }
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    // Number of elements
    int n = sc.nextInt();
    int m = sc.nextInt();
    // array to store non-negative numbers
    int a[] = new int[n];
    for(int i=0;i<n;i++)
      a[i] = sc.nextInt();
    boolean can = findSubsetDivisibleByM(a, n, m);
    if(can == true)
      System.out.println("There exists a subset having sum divisible by m");
    else
      System.out.println("There does not exist any subset having sum divisible by m");
  	}
}
3 3
1 2 4
There exists a subset having sum divisible by m

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

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

ओ (एम ^ 2), कारण आम्हाला केवळ n <= m तेव्हाच समस्येचे निराकरण करावे लागेल. अशाप्रकारे एन साठी वरची बाउंड एम. अशा प्रकारे काळातील गुंतागुंत बहुवचन असते.

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

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