Check if there is any valid sequence divisible by M

A sequence is a collection of objects, in our case it is a collection of integers. The task is to determine whether a sequence of elements using addition and subtraction operators is divisible by M.

Problem Statement

Given an integer M and an integer array. Checks whether there is a valid sequence whose solution is divisible by M using only addition and subtraction between elements.

Example 1

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

Output: TRUE

Explanation - For the given array, there may be a valid sequence {1 2 5} = {8}, which is divisible by 2.

Example 2

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

Output: FALSE

Explanation - For the given array, there cannot be a sequence whose solution is divisible by 4.

Method 1: Violent method

A simple way to solve this problem is to use a recursive function to find all possible sequences of the array, and then check if any sequence is divisible by 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

Example: C implementation

In the following program, we use a recursive method to find all valid sequences and then check if any valid sequence is divisible by 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;
}

Output

TRUE

Time complexity - O(2^n) due to the use of recursion.

Space complexity - O(n) due to recursion stack space.

Method 2: Backtracking

This method is similar to the previous brute-force recursive method, except that using backtracking, we can backtrack the search space to avoid going down a path that we know does not have a valid sequence divisible by 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

Example: C implementation

In the following program, we use backtracking to prune the search space to find the solution to the problem.

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

Output

TRUE

Time complexity - The worst case time complexity is O(2^n), but it is actually better than the brute force method due to the pruning of the search space.

Space Complexity - O(n) due to recursive stack space.

Method 3: Greedy method

The greedy solution to this problem is to first sort the array in ascending order and then greedily apply the addition function if the sum does not exceed M. This method may not give a globally optimal solution, but it will give a local optimal solution.

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

Example: C implementation

In the following program, an array is sorted to find the best local subarray divisible by 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;
}

Output

TRUE

Method 4: Dynamic programming

Using the concept of dynamic programming, in this solution we store the intermediate results of the evaluation. We will create a table with N 1 rows and M columns, and when we do not use array elements, the base case results in % M == 0. Then iterating over all possible remainders modulo M, we update the table.

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

Example: C implementation

In the following program, we decompose the problem into sub-problems and then solve them.

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

Output

TRUE

in conclusion

In summary, to find valid sequences divisible by M, we can apply multiple methods and different relational and spatial analyses, ranging from O(2^n) in the brute force case to O(NM) in the dynamic case Programming is the most efficient way.

The above is the detailed content of Check if there is any valid sequence divisible by M. For more information, please follow other related articles on the PHP Chinese website!