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.
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.
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.
Input: M = 4, arr = {1, 2}
Output: FALSE
Explanation - For the given array, there cannot be a sequence whose solution is divisible by 4.
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.
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
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;
}
TRUE
Time complexity - O(2^n) due to the use of recursion.
Space complexity - O(n) due to recursion stack space.
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.
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
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;
}
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.
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.
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
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;
}
TRUE
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.
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
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;
}
TRUE
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!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
