Vérifiez s'il existe une séquence valide divisible par M

Une séquence est une collection d'objets, dans notre cas c'est une collection d'entiers. La tâche consiste à déterminer si une séquence d'éléments utilisant des opérateurs d'addition et de soustraction est divisible par M.

Énoncé du problème

Étant donné un entier M et un tableau d'entiers. Vérifie s'il existe une séquence valide dont la solution est divisible par M en utilisant uniquement l'addition et la soustraction entre les éléments.

Exemple 1

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

Output: TRUE

Explication - Pour le tableau donné, il peut y avoir une séquence valide {1 + 2 + 5} = {8}, qui est divisible par 2.

Exemple 2

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

Output: FALSE

Explication - Pour le tableau donné, il est impossible d'avoir une séquence dont la solution est divisible par 4.

Méthode 1 : Méthode brutale

Un moyen simple de résoudre ce problème consiste à utiliser une fonction récursive pour trouver toutes les séquences possibles du tableau, puis à vérifier si une séquence est divisible par M.

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

Exemple : implémentation C++

Dans le programme suivant, nous utilisons la méthode récursive pour trouver toutes les séquences valides, puis vérifions si une séquence valide est divisible par M.

#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;
}

Sortie

TRUE

Complexité temporelle - O(2^n) en raison de l'utilisation de la récursivité.

Complexité spatiale - O(n) en raison de l'espace de la pile de récursion.

Méthode 2 : Retour en arrière

Cette méthode est similaire à la méthode récursive précédente par force brute, sauf qu'en utilisant le retour en arrière, nous pouvons revenir en arrière dans l'espace de recherche pour éviter de suivre un chemin dont nous savons qu'il n'a pas de séquence valide divisible par M.

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

Exemple : implémentation C++

Dans le programme ci-dessous, nous utilisons le backtracking pour élaguer l'espace de recherche afin de trouver la solution au problème.

#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;
}

Sortie

TRUE

Complexité temporelle - La complexité temporelle dans le pire des cas est O(2^n), mais elle est en fait meilleure que la méthode par force brute en raison de l'élagage de l'espace de recherche.

Complexité spatiale - O(n) en raison de l'espace de pile récursif.

Méthode 3 : Méthode gourmande

La solution gourmande à ce problème consiste à trier d'abord le tableau par ordre croissant, puis à appliquer goulûment la fonction d'addition si la somme ne dépasse pas M. Cette méthode ne donnera peut-être pas une solution globalement optimale, mais elle donnera une solution optimale locale.

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

Exemple : implémentation C++

Dans le programme suivant, un tableau est trié pour trouver le meilleur sous-tableau local divisible par M.

#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;
}

Sortie

TRUE

Méthode 4 : Programmation dynamique

En utilisant le concept de programmation dynamique, dans cette solution nous stockons les résultats intermédiaires de l'évaluation. Nous allons créer un tableau avec N+1 lignes et M colonnes, et lorsque nous n'utilisons pas d'éléments de tableau, le cas de base donne % M == 0. Puis en itérant sur tous les restes possibles modulo M, nous mettons à jour le tableau.

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

Exemple : implémentation C++

Dans le programme ci-dessous, nous divisons le problème en sous-problèmes puis les résolvons.

#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;
}

Sortie

TRUE

Conclusion

Pour résumer, afin de trouver des séquences valides divisibles par M, nous pouvons appliquer plusieurs méthodes et différentes analyses relationnelles et spatiales, allant de O(2^n) dans le cas de la force brute à O(NM) dans le cas de la programmation dynamique. est la méthode la plus efficace.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!