مائي پاران ورهايل رقم سان ننو حصو


تڪليف جي سطح سخت
بار بار پڇڻ ۾ آرڪسيميم Cisco ڊي شاه سڌو Expedia Myntra پي يو يو
ڪيريو متحرڪ پروگرامنگ

مسئلي جو بيان

مسئلو ”مائي ڊسبليوٽ سِٽ اِن سب سيٽيٽ“ ٻڌائي ٿو ته توهان کي غير منفي انٽيگرز ۽ انٽيگر م ترتيب ڏني وڃي ٿي. ھاڻي توھان کي ڳولھڻ جي ضرورت آھي ته ڇا ھڪڙي سبسيٽ آھي جيڪا رقم M پاران قابل تقسيم آھي. انهي جي سبجيڪٽ جو مجموعو اهو هجڻ گهرجي 0 نتيجو جڏهن اسان هن جي طريقي سان ايم سان لهون.

مثال

مائي پاران ورهايل رقم سان ننو حصو

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

وضاحت

نتيجي طور 1,2 ويل ڪرڻ لاءِ سيٽون هجن {3،2} رقم {4 ، 6} پڻ ڏيو ٿا ڇڪو 3 جنهن جي نتيجي ۾ XNUMX ئي ورهائي سگهجن ٿا XNUMX. اهڙي طرح جواب سچو آهي.

چرچو

تنهنڪري ، اسان پڻ ھڪڙو ساڳيو مسئلو سامھون آيا آھيون جنھن کي چيڪ ڪرڻ لاءِ سبٽ جي رقم هڪ ٽارگيٽ سِم جي برابر آهي. پر هتي اهو پڙتال نه ڪريو ته جيڪڏهن ذيلي رقم ڏنل رقم جي برابر آهي پر اسان کي اهو جانچڻ جي ضرورت آهي ته ذيلي رقم مجموعي طور م. تنهن ڪري اسان مسئلي کي نئين سر ترتيب ڏئي سگهون ٿا جئين اسان کي ڳولڻ جي ضرورت هجي ته جيڪڏهن ذيلي سيٽ آهي سم = م ، 2 مي ، 3 مي ، .. وغيره وغيره. جيڪڏهن ذيلي سيٽ ۾ ڏنل ڏنل قدرن جي برابر رقم آهي. اسين سچا ٻُڌايون ٿا واپس غلط

سو ، سوچڻ بدران اهو طريقو چونڊيو. اسان رقم جو موڊ وٺندا رهون ٿا ۽ جيڪڏهن اسان ڪنهن طرح سان 0. حاصل ڪريون ٿا. اسان کي پڪ آهي ته هتي هڪ سب سيٽ موجود آهي ، جيڪا رقم جي ذريعي m. پر اسان کي انهي کان پهريان ڪجهه ڪرڻ جي ضرورت آهي. جيڪڏهن عنصرن جو تعداد n> = m (نمبر جنهن جي مد ۾ وٺڻ لازمي آهي). پوءِ جواب هميشه موجود آهي ڪبوتر جي اصول سان. اسان کي صرف 0 کان م 1 تائين ڪيسن سان معاملو ڪرڻ جي ضرورت آهي جيڪا n <= m.

تنهن ڪري ، هن طريقي جي پويان مڪمل خيال اهو آهي ته اسان وٽ ڪجهه سيٽون آهن سم = ج ، پوءِ اسان نئون سب سيٽ ٺاهي سگهو ٿا سم = (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)، ڇو ته اسان کي اهو مسئلو فقط حل ڪرڻو آهي جڏهن ن <= م. اھڙيءَ طرح اين لاءِ مٿيون حد آھي. ان ڪري وقت جي پيچيدگي پولينومل آهي.

خلائي پيچيدگي

اي (ايم) ، ڇاڪاڻ ته ڊي پي صف لاءِ گهربل جاءِ لڪي آهي. خلائي صرف ڊي پي ٽيبل کي محفوظ ڪرڻ جي ضرورت ھئي ۽ اھڙي طرح خلائي پيچيدگي لڪير آھي.