Cəmi m-ə bölünən alt dəst

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Arcezium Cisco DE Şou Directi Expedia Mintra PayU
Geyim Dinamik proqramlaşdırmaBaxılıb 73

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Cəmi m-ə bölünən alt dəst” problemi sizə mənfi olmayan tam ədəd və m tam ədədi verildiyini bildirir. İndi m-ə bölünən cəmi olan bir alt qrupun olub olmadığını tapmaq lazımdır. Modunu m ilə götürdüyümüzdə nəticədə alt çoxluğun cəmi 0 verməli.

misal

Cəmi m-ə bölünən alt dəstPin

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

Izahat

{1,2} dəyərləri olan alt dəst, nəticədə 3 verəcəkdir. {2, 4} də 6-ə bölünən nəticə olaraq 3-nı vermək üçün yekunlaşdırın. Beləliklə cavab doğrudur.

Yanaşma

Beləliklə, bunun olub olmadığını yoxlamaq üçün oxşar bir problemlə qarşılaşdıq alt cəmin hədəfi cəminə bərabərdir. Ancaq burada alt cəmin müəyyən bir cəmə bərabər olub olmadığını yoxlayın, ancaq alt cəmin m-ə bölündüyünü yoxlamalıyıq. Beləliklə, cəmi = m, 2m, 3m, .. və s. Olan bir alt dəstin olub olmadığını tapmaq üçün problemi yenidən cəmləşdirə bilərik. Alt hissənin verilən dəyərlərdən hər hansı birinə bərabər bir cəmi varsa. true true false qayıdırıq.

Beləliklə, bu şəkildə düşünmək əvəzinə. Cəmin modunu götürməyə davam edirik və birtəhər bir 0 alsaq, cəmin m-ə bölünən alt hissəsinin mövcud olduğuna əminik. Ancaq bundan əvvəl bir şeyə diqqət yetirməliyik. Elementlərin sayı n> = m (modu alacaq say). O zaman cavab həmişə Göyərçin deliği prinsipinə görə mövcuddur. Yalnız n <= m olan 0-dan m-1 cəmi olan hallarla məşğul olmalıyıq.

Beləliklə, bu yanaşmanın arxasındakı bütün fikir budur ki, cəmi = j olan bəzi alt dəstlərimiz var, onda cəmi = (j + cari_element)% m olan yeni alt qruplar yarada bilərik. Və beləcə özümüzü dolduracağıq Dinamik proqramlaşdırma Cədvəl.

Kodu

C ++ kodu, m-ə bölünən cəmi

#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

Cəmi m-ə bölünən alt dəst üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (M ^ 2), çünki problemi yalnız n <= m olduqda həll etməliyik. Beləliklə n üçün yuxarı sərhəd m-dir. Beləliklə zamanın mürəkkəbliyi polinomdur.

Kosmik Mürəkkəblik

O (M), dp dizisi üçün lazım olan yer xətti olduğu üçün. Yalnız dp cədvəlinin saxlanması üçün yer tələb olunurdu və beləliklə yerin mürəkkəbliyi xətti olur.

Crack Sistemi Dizayn Müsahibələri
Translate »