检查任何有效序列是否可以被 M 整除

序列是对象的集合，在我们的例子中，它是整数的集合。任务是找出元素中使用加法和减法运算符的序列是否可以被 M 整除。

问题陈述

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

示例 1

输入:M = 2，arr = {1, 2, 5}

输出:TRUE

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

示例 2

输入:M = 4，arr = {1, 2}

输出: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;

// 递归函数用于查找有效序列是否可被 M 整除
bool divisible(int M, int arr[], int index, int sum, int n){

   // 当数组结束时检查能否被 M 整除
   if (index == n)  {
      if (sum % M == 0){
         return true;
      }
      return false;
   }
   
   // 如果加法或减法其中一个为真，则返回 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;

// 函数用于查找有效序列是否可被 M 整除
bool divisible(int M, int arr[], int index, int sum, int n){

    // 检查数组结束时 M 的整除性
    if (index == n){
        if (sum % M == 0){
            return true;
        }
    	return false;
    }
    
    // 检查 sum + arr[index] 的整除性
    if (divisible(M, arr, index + 1, sum + arr[index], n)){
        return true;
    }
    
    // 检查 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;

// 贪婪函数用于查找有效序列是否可被 M 整除
bool divisible(int M, vector<int> &arr){
   int sum = 0;
   for (int i = 0; i < arr.size(); i++) {
      sum += arr[i];
   }
   
   // 检查所有元素的总和是否可以被 M 整除
   if (sum % M == 0){
      return true;
   }
   
   sort(arr.begin(), arr.end());
   int i = 0, j = arr.size() - 1;
   while (i < j){
   
      // 检查数组中最大元素与最小元素之间的差是否可以被 M 整除
      if ((arr[j] - arr[i]) % M == 0){
         return true;
      }
      
      // 删除最大或最小元素不会影响总和的可整除性
      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;

// 函数用于查找有效序列是否可被 M 整除
bool divisible(int arr[], int M, int N){

    // 创建大小为 N+1 * M 的 dp 表
    vector<vector<bool> > dp(N + 1, vector<bool>(M, false));
    
    // 基本情况
    dp[0][0] = true;
    
    // 对每个元素迭代 j 模 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;
}

输出

TRUE

结论

总之，为了找到一个能被 M 整除的有效序列，我们可以应用多种方法，时间和空间分析范围从强力攻击的 O(2^n) 到动态规划的 O(NM)(这是最有效的方法)。

相关文章

• 背面检测方法
• 检查字符串是否可以分成两个子序列，使得和的乘积为奇数
• 检查给定树的左视图是否已排序
• C++17 中的 std::string_view 类
• 检查是否可以通过将括号向两端移动最多 K 次来获得平衡括号
• 检查是否存在 2 * K + 1 个非空字符串，它们的连接构成给定的字符串
• 检查给定句子中子字符串 S1 是否出现在子字符串 S2 的任何出现之后
• 检查给定字符串的任何排列是否按字典顺序大于另一个给定字符串
• 在执行 K 个操作的所有可能选择后，给定二进制字符串中设置位数的平均值
• 通过执行交换操作检查两个字符串数组是否相等