Given an array arr[] of size N, the task is to find the maximum sum of a subset of the array such that the sum is divisible by M and the Xor of the subsequence is 0.
Examples:
Input: A = {2, 3, 2, 5, 5}, M = 5
Output: 10
Explanation: maximum sum will be by selecting subset {5, 5} which is 10, also its xor 5 ^ 5 is zero and sum is divisible by 5. {2, 2, 5, 5} cannot be answer since its xor is zero but its sum is not divisible by 5.Input: A = {7, 7, 1, 2, 3}, M = 5
Output: 20
Naive Approach: The article can be solved based on the following idea:
Basic way to solve this is to generate all possible combinations by using recursive brute force.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve the following problem efficiently.
- dp[i][j][k] = X represents sum of elements chosen from first i array elements and j being its sum and k is its xor.
- It can be observed that there are N * sum * XOR states but the recursive function is called 2n times. That means that some states are called repeatedly. So the idea is to store the value of states. This can be done using recursive structure intact and just store the value in an array or HashMap and whenever the function is called, return the value stored without computing .
Follow the steps below to solve the problem:
- Create a recursive function that takes three parameters one is the i which represents the ith element of the array, one is the sum which represents the sum of the subset chosen till ith element of an array and j being its sum and k is its xor.
- Call recursive functions for the cases by taking ith element and not taking ith element in sum.
- Check the base case if the sum or XOR is not equal to zero if true return an invalid number else return 0.
- Create an 3d array of dp[101][101][101] with initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][sum][XOR].
- If the answer for a particular state is already computed then just return dp[i][sum][XOR].
Below is the code implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // initializing the dp table with - 1 int dp[101][101][101]; // Recursive function to find maximum sum // of array which is divisible by M and // xor of all elements is zero. int recur( int i, int sum, int XOR, int arr[], int N, int M) { // base case if (i == N) { // pruning if sum % M is not zero or // XOR of elements is not zero it will // be invalid answer. if (sum != 0 or XOR != 0) return -1e9; return 0; } // returning dp[i][sum][XOR] if current state // is already calculated. if (dp[i][sum][XOR] != -1) return dp[i][sum][XOR]; // if current element not taken in sum. int ans = recur(i + 1, sum, XOR, arr, N, M); // if current element is taken into sum int save = recur(i + 1, (sum + arr[i]) % M, (XOR ^ arr[i]), arr, N, M); // if answer is valid then only update the answer if (save != -1e9) ans = max(ans, save + arr[i]); // saving and returning sum return dp[i][sum][XOR] = ans; } // Function to Find maximum element from // given array such that sum divisible by // M and xor of its elements is zero. void maxSumDivisibleByM( int arr[], int N, int M) { // initializing dp table with - 1 memset (dp, -1, sizeof (dp)); int ans = recur(0, 0, 0, arr, N, M); if (ans == -1e9) cout << -1 << endl; else cout << ans << endl; } // Driver Code int main() { // input int arr[] = { 2, 3, 2, 5, 5 }; int M = 5; int N = sizeof (arr) / sizeof (arr[0]); // Function Call maxSumDivisibleByM(arr, N, M); // input2 int arr1[] = { 7, 7, 1, 2, 3 }; int M1 = 5; int N1 = sizeof (arr1) / sizeof (arr1[0]); // Function Call maxSumDivisibleByM(arr1, N1, M1); return 0; } |
Java
// Java code to implement the approach import java.io.*; public class Main { // initializing the dp table with - 1 static int [][][] dp = new int [ 101 ][ 101 ][ 101 ]; // Recursive function to find maximum sum // of array which is divisible by M and // xor of all elements is zero. static int recur( int i, int sum, int XOR, int [] arr, int N, int M) { // base case if (i == N) { // pruning if sum % M is not zero or // XOR of elements is not zero it will // be invalid answer. if (sum != 0 || XOR != 0 ) return -( int )1e9; return 0 ; } // returning dp[i][sum][XOR] if current state // is already calculated. if (dp[i][sum][XOR] != - 1 ) return dp[i][sum][XOR]; // if current element not taken in sum. int ans = recur(i + 1 , sum, XOR, arr, N, M); // if current element is taken into sum int save = recur(i + 1 , (sum + arr[i]) % M, (XOR ^ arr[i]), arr, N, M); // if answer is valid then only update the answer if (save != -( int )1e9) ans = Math.max(ans, save + arr[i]); // saving and returning sum return dp[i][sum][XOR] = ans; } static void maxSumDivisibleByM( int [] arr, int N, int M) { // initializing dp table with - 1 for ( int i = 0 ; i < 101 ; i++) { for ( int j = 0 ; j < 101 ; j++) { for ( int k = 0 ; k < 101 ; k++) { dp[i][j][k] = - 1 ; } } } int ans = recur( 0 , 0 , 0 , arr, N, M); if (ans == -( int )1e9) System.out.println(- 1 ); else System.out.println(ans); } public static void main(String[] args) { // input int [] arr = { 2 , 3 , 2 , 5 , 5 }; int M = 5 ; int N = arr.length; // Function Call maxSumDivisibleByM(arr, N, M); // input2 int [] arr1 = { 7 , 7 , 1 , 2 , 3 }; int M1 = 5 ; int N1 = arr1.length; // Function Call maxSumDivisibleByM(arr1, N1, M1); } } // This code is contributed by lokesh. |
Python3
import sys # Recursive function to find maximum sum # of array which is divisible by M and # xor of all elements is zero. def recur(i, sum , XOR, arr, N, M, dp): # base case if i = = N: # pruning if sum % M is not zero or # XOR of elements is not zero it will # be invalid answer. if sum ! = 0 or XOR ! = 0 : return - 1e9 return 0 # returning dp[i][sum][XOR] if current state # is already calculated. if dp[i][ sum ][XOR] ! = - 1 : return dp[i][ sum ][XOR] # if current element not taken in sum. ans = recur(i + 1 , sum , XOR, arr, N, M, dp) # if current element is taken into sum save = recur(i + 1 , ( sum + arr[i]) % M, (XOR ^ arr[i]), arr, N, M, dp) # if answer is valid then only update the answer if save ! = - 1e9 : ans = max (ans, save + arr[i]) # saving and returning sum dp[i][ sum ][XOR] = ans return ans # Function to Find maximum element from # given array such that sum divisible by # M and xor of its elements is zero. def maxSumDivisibleByM(arr, N, M): # initializing dp table with - 1 dp = [[[ - 1 for _ in range ( 101 )] for _ in range ( 101 )] for _ in range ( 101 )] ans = recur( 0 , 0 , 0 , arr, N, M, dp) if ans = = - 1e9 : print ( - 1 ) else : print (ans) #Driver code arr = [ 2 , 3 , 2 , 5 , 5 ] M = 5 N = len (arr) # Function Call maxSumDivisibleByM(arr, N, M) arr1 = [ 7 , 7 , 1 , 2 , 3 ] M1 = 5 N1 = len (arr1) # Function Call maxSumDivisibleByM(arr1, N1, M1) #This code is contributed by Potta Lokesh |
C#
// C# code to implement the approach using System; public class GFG { // initializing the dp table with - 1 static int [,,] dp = new int [101,101,101]; // Recursive function to find maximum sum // of array which is divisible by M and // xor of all elements is zero. static int recur( int i, int sum, int XOR, int [] arr, int N, int M) { // base case if (i == N) { // pruning if sum % M is not zero or // XOR of elements is not zero it will // be invalid answer. if (sum != 0 || XOR != 0) return -( int )1e9; return 0; } // returning dp[i,sum,XOR] if current state // is already calculated. if (dp[i,sum,XOR] != -1) return dp[i,sum,XOR]; // if current element not taken in sum. int ans = recur(i + 1, sum, XOR, arr, N, M); // if current element is taken into sum int save = recur(i + 1, (sum + arr[i]) % M, (XOR ^ arr[i]), arr, N, M); // if answer is valid then only update the answer if (save != -( int )1e9) ans = Math.Max(ans, save + arr[i]); // saving and returning sum return dp[i,sum,XOR] = ans; } static void maxSumDivisibleByM( int [] arr, int N, int M) { // initializing dp table with - 1 for ( int i = 0; i < 101; i++) { for ( int j = 0; j < 101; j++) { for ( int k = 0; k < 101; k++) { dp[i,j,k] = -1; } } } int ans = recur(0, 0, 0, arr, N, M); if (ans == -( int )1e9) Console.WriteLine(-1); else Console.WriteLine(ans); } static public void Main () { // input int [] arr = { 2, 3, 2, 5, 5 }; int M = 5; int N = arr.Length; // Function Call maxSumDivisibleByM(arr, N, M); // input2 int [] arr1 = { 7, 7, 1, 2, 3 }; int M1 = 5; int N1 = arr1.Length; // Function Call maxSumDivisibleByM(arr1, N1, M1); } } // This code is contributed by Pushpesh Raj. |
Javascript
// JavaScript code for the above approach let dp = new Array(101); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(101); } for (let i = 0; i < 101; i++) { for (let j = 0; j < 101; j++) { dp[i][j] = new Array(101).fill(-1) } } // Recursive function to find maximum sum // of array which is divisible by M and // xor of all elements is zero. function recur(i, sum, XOR, arr, N, M) { // base case if (i == N) { // pruning if sum % M is not zero or // XOR of elements is not zero it will // be invalid answer. if (sum != 0 || XOR != 0) return -1e9 return 0 } // returning dp[i][sum][XOR] if current state // is already calculated. if (dp[i][sum][XOR] != -1) return dp[i][sum][XOR] // if current element not taken in sum. let ans = recur(i + 1, sum, XOR, arr, N, M) // if current element is taken leto sum let save = recur(i + 1, (sum + arr[i]) % M, (XOR ^ arr[i]), arr, N, M) // if answer is valid then only update the answer if (save != -1e9) ans = Math.max(ans, save + arr[i]) // saving and returning sum return dp[i][sum][XOR] = ans } // Function to Find maximum element from // given array such that sum divisible by // M and xor of its elements is zero. function maxSumDivisibleByM(arr, N, M) { let ans = recur(0, 0, 0, arr, N, M) if (ans == -1e9) console.log(-1) else console.log(ans) } // Driver Code // input let arr = [2, 3, 2, 5, 5] let M = 5 let N = arr.length // Function Call maxSumDivisibleByM(arr, N, M) for (let i = 0; i < 101; i++) { for (let j = 0; j < 101; j++) { for (let k = 0; k < 101; k++) dp[i][j][k] = -1; } } // input2 let arr1 = [7, 7, 1, 2, 3] let M1 = 5 let N1 = arr1.length // Function Call maxSumDivisibleByM(arr1, N1, M1) // This code is contributed by poojaagarwal2. |
10 20
Time Complexity: O(N * M * K)
Auxiliary Space: O(N * M * K)), Where K is the maximum xor of array elements.
Related Articles :
- Bitwise Operators in C/C++
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
- Introduction to Array – Data Structures and Algorithms Tutorials
- Introduction to Recursion – Data Structures and Algorithms
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!