C++ 检查是否有任何有效的序列能被M整除

一个序列是一组对象，在我们的示例中，它是一组整数。任务是找到使用加法和减法运算符的元素中是否可以找到一个能被M整除的有效序列。

问题陈述

给定一个整数M和一个整数数组。只使用元素之间的加法和减法运算，检查是否存在一个有效的序列，其解能被M整除。

示例1

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

Output: TRUE

解释 − 对于给定的数组，存在一个有效的序列{1 + 2 + 5} = {8}，它可以被2整除。

示例2

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

Output: FALSE

解释 − 对于给定的数组，没有任何序列的解能被4整除。

方法1：蛮力方法

这个问题的一个简单解法是使用递归函数找出数组的所有可能序列，然后检查是否有任何序列能被M整除。

伪代码

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

示例：C++ 实现

在下面的程序中，我们使用递归方法来查找所有的有效序列，然后检查是否有任何有效序列可以被 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;
}

输出

TRUE

时间复杂度 – 由于使用递归，为O(2^n)。

空间复杂度 – 由于递归栈空间，为O(n)。

方法2：回溯法

这种方法与上面的暴力递归方法类似，不同之处在于使用回溯法我们可以回溯搜索空间，以避免进入我们知道不会有有效可被M整除序列的路径。

伪代码

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

示例：C++ 实现

在下面的程序中，我们使用回溯法来剪枝搜索空间，以找到问题的解决方案。

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

输出

TRUE

时间复杂度 - 对于最坏情况下的时间复杂度为O(2^n)，但在实践中，由于搜索空间的修剪，它比暴力方法要好。

空间复杂度 - 由于递归堆栈空间而为O(n)。

方法3：贪心算法

问题的贪心解法是先按递增顺序对数组进行排序，然后贪心地进行加法运算，如果和不超过M，则应用该加法。这种方法可能不能得到全局最优解，但可以得到局部最优解。

伪代码

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

示例：C++实现

在以下程序中，数组被排序以找到最优的可以被 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;
}

输出

TRUE

方法4: 动态规划

使用动态规划的概念，在这个解决方案中我们存储了评估的中间结果。我们将创建一个N+1行和M列的表，当我们不使用数组的任何元素时，结果%M == 0为基本情况。然后迭代所有可能的余数模M，更新表格。

伪代码

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

示例：C++实现

在以下程序中，我们将问题分解为子问题，然后解决它们。

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