Überprüfen Sie, ob es eine gültige durch M teilbare Folge gibt

Eine Sequenz ist eine Sammlung von Objekten, in unserem Fall eine Sammlung von ganzen Zahlen. Die Aufgabe besteht darin, mithilfe von Additions- und Subtraktionsoperatoren zu bestimmen, ob eine Folge von Elementen durch M teilbar ist.

Problemstellung

Gegeben sind eine ganze Zahl M und ein ganzzahliges Array. Überprüft, ob es eine gültige Folge gibt, deren Lösung durch M teilbar ist, indem nur Addition und Subtraktion zwischen Elementen verwendet wird.

Beispiel 1

Input: M = 2, arr = {1, 2, 5}

Output: TRUE

Erklärung – Für das gegebene Array kann es eine gültige Folge {1 + 2 + 5} = {8} geben, die durch 2 teilbar ist.

Beispiel 2

Input: M = 4, arr = {1, 2}

Output: FALSE

Erklärung – Für das gegebene Array ist es unmöglich, eine Sequenz zu haben, deren Lösung durch 4 teilbar ist.

Methode 1: Brutale Methode

Eine einfache Möglichkeit, dieses Problem zu lösen, besteht darin, eine rekursive Funktion zu verwenden, um alle möglichen Sequenzen des Arrays zu finden und dann zu prüfen, ob eine Sequenz durch M teilbar ist.

Pseudocode

procedure divisible (M, arr[], index, sum, n)
   if index == n
      if sum is a multiple of M
         ans = TRUE
      end if
      ans = false
   end if
   divisible(M, arr, index + 1, sum + arr[index], n) or divisible(M, arr, index + 1, sum - arr[index], n)
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm verwenden wir die rekursive Methode, um alle gültigen Sequenzen zu finden und prüfen dann, ob eine gültige Sequenz durch M teilbar ist.

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

// Recusive function to find if a valid sequence is divisible by M or not
bool divisible(int M, int arr[], int index, int sum, int n){

   // Cheking the divisiblilty by M when the array ends
   if (index == n)  {
      if (sum % M == 0){
         return true;
      }
      return false;
   }
   
   // If either of addition or subtraction is true, return true
   return divisible(M, arr, index + 1, sum + arr[index], n) || divisible(M, arr, index + 1, sum - arr[index], n);
}
int main(){
   int M = 4, arr[2] = {1, 5};
   if (divisible(M, arr, 0, 0, 2)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Ausgabe

TRUE

Zeitliche Komplexität – O(2^n) aufgrund der Verwendung von Rekursion.

Raumkomplexität – O(n) aufgrund des rekursiven Stapelraums.

Methode 2: Backtracking

Diese Methode ähnelt der vorherigen rekursiven Brute-Force-Methode, außer dass wir mithilfe von Backtracking den Suchraum zurückverfolgen können, um zu vermeiden, einen Pfad einzuschlagen, von dem wir wissen, dass er keine gültige, durch M teilbare Sequenz hat.

Pseudocode

procedure divisible (M, arr[], index, sum, n)
   if index == n
      if sum is a multiple of M
         ans = TRUE
      end if
      ans = false
   end if
   if divisible(M, arr, index + 1, sum + arr[index], n)
      ans = true
   end if
   if divisible(M, arr, index + 1, sum - arr[index], n)
      ans = true
   end if
   ans = false
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm verwenden wir Backtracking, um den Suchraum zu beschneiden und die Lösung für das Problem zu finden.

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

// Function to find if a valid sequence is divisible by M or not
bool divisible(int M, int arr[], int index, int sum, int n){

   // Cheking the divisiblilty by M when the array ends
   if (index == n){
      if (sum % M == 0){
         return true;
      }
      return false;
   }
   
   // Checking the divisibility of sum + arr[index]
   if (divisible(M, arr, index + 1, sum + arr[index], n)){
      return true;
   }
   
   // Checking the divisibility of sum - arr[index]
   if (divisible(M, arr, index + 1, sum - arr[index], n)){
      return true;
   }
   return false;
}
int main(){
   int M = 4, arr[2] = {1, 5};
   if (divisible(M, arr, 0, 0, 2)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Ausgabe

TRUE

Zeitkomplexität – Die Zeitkomplexität im schlimmsten Fall ist O(2^n), aber aufgrund der Beschneidung des Suchraums ist sie tatsächlich besser als die Brute-Force-Methode.

Raumkomplexität – O(n) aufgrund des rekursiven Stapelraums.

Methode 3: Greedy-Methode

Die gierige Lösung für dieses Problem besteht darin, das Array zunächst in aufsteigender Reihenfolge zu sortieren und dann die Additionsfunktion gierig anzuwenden, wenn die Summe M nicht überschreitet. Diese Methode liefert möglicherweise keine global optimale Lösung, wohl aber eine lokal optimale Lösung.

Pseudocode

procedure divisible (M, arr[])
   sum = 0
   for i = 1 to end of arr
      sum = sum + arr[i]
   if sum is divisible by M
      ans = true
   end if
   sort array arr[]
   i = 0
   j = last index of array
   while i < j
      if arr[j] - arr[i] is divisible by M
         ans = true
      end if
      if sum % M == (sum - arr[j]) % M
         sum = sum - arr[j]
         j = j - 1
      else
         sum = sum - arr[i]
         i = i + 1
      end if
   ans = false
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm wird ein Array sortiert, um das beste lokale Subarray zu finden, das durch M teilbar ist.

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

// Greedy function to find if a valid sequence is divisible by M or not
bool divisible(int M, vector<int> &arr){
   int sum = 0;
   for (int i = 0; i < arr.size(); i++) {
      sum += arr[i];
   }
   
   // Checking if sumof all elements is divisible by M
   if (sum % M == 0){
      return true;
   }
   
   sort(arr.begin(), arr.end());
   int i = 0, j = arr.size() - 1;
   while (i < j){
   
      // Checking if the difference between the largest and smallest element at a time in the array is divisible by M
      if ((arr[j] - arr[i]) % M == 0){
         return true;
      }
      
      // Removing either the largest or smallest element based on which does not affect the sum's divisibility
      if (sum % M == (sum - arr[i]) % M){
         sum -= arr[i];
         i++;
      }
      else{
         sum -= arr[j];
         j--;
      }
   }
   return false;
}
int main(){
   int M = 4;
   int array[2] = {1, 3};
   vector<int> arr(array, array + 2);
   if (divisible(M, arr)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Ausgabe

TRUE

Methode 4: Dynamische Programmierung

Anhand des Konzepts der dynamischen Programmierung speichern wir in dieser Lösung die Zwischenergebnisse der Auswertung. Wir erstellen eine Tabelle mit N+1 Zeilen und M Spalten, und wenn wir keine Array-Elemente verwenden, ergibt sich im Basisfall %M == 0. Dann iterieren wir modulo M über alle möglichen Reste und aktualisieren die Tabelle.

Pseudocode

procedure divisible (arr[], M , N)
   dp[N+1][M] = false
   dp[0][0] = true 
   for i = 1 to N
      for i = j to M
         mod = arr[ i- 1] % M
         dp[i][j] = dp[i - 1][(j - mod + M) % M] or dp[i - 1][(j + mod) % M]
   ans = dp[N][0]
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm zerlegen wir das Problem in Teilprobleme und lösen sie dann.

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

// Function to find if a valid sequence is divisible by M or not
bool divisible(int arr[], int M, int N){

   // Creating the dp table of size N+1 * M
   vector<vector<bool> > dp(N + 1, vector<bool>(M, false));
   
   // Base case
   dp[0][0] = true;
   
   // For each element iterating over all possible remainders j modulo M
   for (int i = 1; i <= N; i++){
      for (int j = 0; j < M; j++){
         int mod = arr[i - 1] % M;
         
         // Either exclude or include the current element in the table
         dp[i][j] = dp[i - 1][(j - mod + M) % M] || dp[i - 1][(j + mod) % M];
      }
   }
   return dp[N][0];
}
int main(){
   int M = 4;
   int arr[2] = {1, 3};
   if (divisible(arr, M, 2)){
      cout << "TRUE";
   }
   else{
      cout << " FALSE";
   }
   return 0;
}

Ausgabe

TRUE

Fazit

Zusammenfassend lässt sich sagen, dass wir, um gültige durch M teilbare Sequenzen zu finden, mehrere Methoden und verschiedene relationale und räumliche Analysen anwenden können, die von O(2^n) im Brute-Force-Fall bis zu O(NM) im dynamischen Fall reichen ist die effektivste Methode.

Das obige ist der detaillierte Inhalt vonÜberprüfen Sie, ob es eine gültige durch M teilbare Folge gibt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!