Given an array of integers and a number K. The task is to find the maximum sum which is divisible by K from the given array.
Examples:
Input: arr[] = {3, 6, 5, 1, 8}, k = 3
Output: 18
Explanation: 18 is formed by the elements 3, 6, 1, 8.
Input: arr = { 43, 1, 17, 26, 15 } , k = 16
Output: 32
Explanation: 32 is formed by the elements 17, 15.
Naive Approach: Recursively check all the possible combinations to find the solution. The solution is of exponential time complexity and thus inefficient.
Efficient Approach: A dynamic programming approach by maintaining a 2-D array dp which stores the state of variable sum and i (where sum is the current sum and i is the ith index of integer array). By recurring over all elements, calculate the sum including the element at index i as well as excluding it and check if divisible by k. If so, store the maximum of them in dp[i][sum] and return.
Below code is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int dp[1001][1001];// Function to return the maximum sum// divisible by k from elements of vint find_max(int i, int sum, vector<int>& v,int k){ if (i == v.size()) return 0; if (dp[i][sum] != -1) return dp[i][sum]; int ans = 0; // check if sum of elements excluding the // current one is divisible by k if ((sum + find_max(i + 1, sum, v, k)) % k == 0) ans = find_max(i + 1, sum, v, k); // check if sum of elements including the // current one is divisible by k if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) % k == 0) // Store the maximum ans = max(ans, v[i] + find_max(i + 1, (sum + v[i]) % k,v, k)); return dp[i][sum] = ans;}// Driver codeint main(){ vector<int> arr = { 43, 1, 17, 26, 15 }; int k = 16; memset(dp, -1, sizeof(dp)); cout << find_max(0, 0, arr, k);} |
Java
class GFG{ static int [][]dp = new int[1001][1001]; // Function to return the maximum sum// divisible by k from elements of vstatic int find_max(int i, int sum, int []v, int k){ if (i == v.length) return 0; if (dp[i][sum] != -1) return dp[i][sum]; int ans = 0; // check if sum of elements excluding the // current one is divisible by k if ((sum + find_max(i + 1, sum, v, k)) % k == 0) ans = find_max(i + 1, sum, v, k); // check if sum of elements including the // current one is divisible by k if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) % k == 0) // Store the maximum ans = Math.max(ans, v[i] + find_max(i + 1, (sum + v[i]) % k, v, k)); return dp[i][sum] = ans;} // Driver codepublic static void main(String[] args){ int []arr = { 43, 1, 17, 26, 15 }; int k = 16; for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) dp[i][j] = -1; System.out.print(find_max(0, 0, arr, k));}}// This code is contributed by 29AjayKumar |
Python 3
# Python3 implementationdp = [[-1 for i in range(1001)] for j in range(1001)]# Function to return the maximum sum# divisible by k from elements of vdef find_max(i, sum, v, k): if (i == len(v)): return 0 if (dp[i][sum] != -1): return dp[i][sum] ans = 0 # check if sum of elements excluding the # current one is divisible by k if ((sum + find_max(i + 1, sum, v, k)) % k == 0): ans = find_max(i + 1, sum, v, k) # check if sum of elements including the # current one is divisible by k if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) % k == 0): # Store the maximum ans = max(ans, v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) dp[i][sum] = ans return dp[i][sum]# Driver codeif __name__ == '__main__': arr = [43, 1, 17, 26, 15] k = 16 print(find_max(0, 0, arr, k))# This code is contributed by Surendra_Gangwar |
C#
using System;class GFG{ static int [,]dp = new int[1001,1001]; // Function to return the maximum sum// divisible by k from elements of vstatic int find_max(int i, int sum, int []v, int k){ if (i == v.Length) return 0; if (dp[i,sum] != -1) return dp[i,sum]; int ans = 0; // check if sum of elements excluding the // current one is divisible by k if ((sum + find_max(i + 1, sum, v, k)) % k == 0) ans = find_max(i + 1, sum, v, k); // check if sum of elements including the // current one is divisible by k if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) % k == 0) // Store the maximum ans = Math.Max(ans, v[i] + find_max(i + 1, (sum + v[i]) % k, v, k)); return dp[i, sum] = ans;} // Driver codepublic static void Main(String[] args){ int []arr = { 43, 1, 17, 26, 15 }; int k = 16; for (int i = 0; i < 1001; i++) for (int j = 0; j < 1001; j++) dp[i,j] = -1; Console.Write(find_max(0, 0, arr, k));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approachlet dp = new Array(1000 + 1); // Function to return the maximum sum// divisible by k from elements of vfunction find_max(i, sum, v, k){ if (i == v.length) return 0; if (dp[i][sum] != -1) return dp[i][sum]; let ans = 0; // check if sum of elements excluding the // current one is divisible by k if ((sum + find_max(i + 1, sum, v, k)) % k == 0) ans = find_max(i + 1, sum, v, k); // check if sum of elements including the // current one is divisible by k if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) % k == 0) // Store the maximum ans = Math.max(ans, v[i] + find_max(i + 1, (sum + v[i]) % k,v, k)); return dp[i][sum] = ans;} // Driver Code let arr = [ 43, 1, 17, 26, 15 ]; let k = 16; // Loop to create 2D array using 1D array for (var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } for (var i = 0; i < dp.length; i++) { for (var j = 0; j < dp.length; j++) { dp[i][j] = -1; } } document.write(find_max(0, 0, arr, k)); // This code is contributed by Dharanendra L V.</script> |
Output
32
Time Complexity: O(n*2^n)
Auxiliary Space: O(n*k)
Iterative implementation using top down dp:
We will be using the index and the modulus value of the sum as our states of dp. dp[i][j] would store the maximum sum of the array till ith index whose modulus is j.
C++
#include <bits/stdc++.h>using namespace std;int main(){ int k=16; vector<int>arr={ 43, 1, 17, 26, 15 } ; int n=arr.size(); vector<vector<int>> dp(n+2, vector<int>(k, 0)); for (int i = 1; i <= n; i++) { for (int j = 0; j < k ; j++) { dp[i][j] = dp[i - 1][j]; } dp[i][arr[i - 1] % k] = max(dp[i][arr[i - 1] % k], arr[i - 1]); for (int j = 0; j < k; j++) { int m = (j + arr[i - 1]) % k; if (dp[i - 1][j] != 0) dp[i][m] = max(dp[i][m],arr[i - 1] + dp[i - 1][j]); } } cout <<dp[n][0]; return 0;} |
Java
import java.util.*;class GFG { public static void main(String[] args) { int k = 16; int[] arr = { 43, 1, 17, 26, 15 }; int n = arr.length; int[][] dp = new int[n + 2][k]; for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { dp[i][j] = dp[i - 1][j]; } dp[i][arr[i - 1] % k] = Math.max( dp[i][arr[i - 1] % k], arr[i - 1]); for (int j = 0; j < k; j++) { int m = (j + arr[i - 1]) % k; if (dp[i - 1][j] != 0) dp[i][m] = Math.max(dp[i][m], arr[i - 1] + dp[i - 1][j]); } } System.out.print(dp[n][0]); }}// This code is contributed by ukasp. |
Python3
k = 16arr = [ 43, 1, 17, 26, 15 ]n = len(arr)dp = [[0 for i in range(k)] for j in range(n+2)]for i in range(1, n+1): for j in range(k): dp[i][j] = dp[i - 1][j] dp[i][arr[i - 1] % k] = max(dp[i][arr[i - 1] % k], arr[i - 1]) for j in range(k): m = (j + arr[i - 1]) % k if dp[i - 1][j] != 0: dp[i][m] = max(dp[i][m],arr[i - 1] + dp[i - 1][j]) print(dp[n][0])# This code is contributed by suresh07. |
C#
using System;class GFG { static void Main() { int k = 16; int[] arr = { 43, 1, 17, 26, 15 }; int n = arr.Length; int[,] dp = new int[n + 2, k]; for (int i = 1; i <= n; i++) { for (int j = 0; j < k ; j++) { dp[i,j] = dp[i - 1,j]; } dp[i,arr[i - 1] % k] = Math.Max(dp[i,arr[i - 1] % k], arr[i - 1]); for (int j = 0; j < k; j++) { int m = (j + arr[i - 1]) % k; if (dp[i - 1,j] != 0) dp[i,m] = Math.Max(dp[i,m],arr[i - 1] + dp[i - 1,j]); } } Console.Write(dp[n,0]); }}// This code is contributed by divyesh072019. |
Javascript
<script> let k = 16; let arr = [ 43, 1, 17, 26, 15 ] ; let n = arr.length; let dp = new Array(n+2); for(let i = 0; i < n+2; i++) { dp[i] = new Array(k); for(let j = 0; j < k; j++) { dp[i][j] = 0; } } for (let i = 1; i <= n; i++) { for (let j = 0; j < k ; j++) { dp[i][j] = dp[i - 1][j]; } dp[i][arr[i - 1] % k] = Math.max(dp[i][arr[i - 1] % k], arr[i - 1]); for (let j = 0; j < k; j++) { let m = (j + arr[i - 1]) % k; if (dp[i - 1][j] != 0) dp[i][m] = Math.max(dp[i][m],arr[i - 1] + dp[i - 1][j]); } } document.write(dp[n][0]); // This code is contributed by mukesh07.</script> |
Output
32
Time Complexity: O(N*K)
Auxiliary Space: O(N*K)
Efficient approach: Space optimization
In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use two vectors curr and prev that keep track of current and previous row of DP.
Implementation Steps:
- Initialize two vectors curr and prev to keep track of only current and previous row of Dp with 0.
- Now iterative over subproblems and get the current computation.
- While iteration initialize curr vector.
- Now compute the current value by the help of prev vector and store that value in curr.
- After every iteration store values of curr vector in prev vector for further iteration.
- At last return the answer stored in curr[0].
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// Function to return the maximum sum// divisible by k from elements of vint findMax(vector<int> arr , int k , int n){ // initialize two vectors curr and prev to keep // track of only current and previous row of Dp vector<int>prev(k+1, 0); vector<int>curr(k+1, 0); // iterative over subproblems and get the current computation for (int i = 1; i <= n; i++) { // initialize curr vector for (int j = 0; j < k ; j++) { curr[j] = prev[j]; } // get the current value by the help of previous row curr[arr[i - 1] % k] = max(curr[arr[i - 1] % k], arr[i - 1]); for (int j = 0; j < k; j++) { int m = (j + arr[i - 1]) % k; if (prev[j] != 0) curr[m] = max(curr[m],arr[i - 1] + prev[j]); } // assigning curr to prev for further iteration prev = curr; } // print result return curr[0];}// Driver codeint main(){ int k=16; vector<int>arr={ 43, 1, 17, 26, 15 } ; int n=arr.size(); cout << findMax(arr, k , n); return 0;} |
Java
import java.util.*;public class Main { // Function to return the maximum sum // divisible by k from elements of v static int findMax(List<Integer> arr, int k, int n) { // initialize two arrays curr and prev to keep // track of only current and previous row of Dp int[] prev = new int[k+1]; int[] curr = new int[k+1]; // iterative over subproblems and get the current computation for (int i = 1; i <= n; i++) { // initialize curr array for (int j = 0; j < k ; j++) { curr[j] = prev[j]; } // get the current value by the help of previous row curr[arr.get(i - 1) % k] = Math.max(curr[arr.get(i - 1) % k], arr.get(i - 1)); for (int j = 0; j < k; j++) { int m = (j + arr.get(i - 1)) % k; if (prev[j] != 0) curr[m] = Math.max(curr[m], arr.get(i - 1) + prev[j]); } // assigning curr to prev for further iteration prev = curr.clone(); } // print result return curr[0]; } // Driver code public static void main(String[] args) { int k = 16; List<Integer> arr = new ArrayList<>(Arrays.asList(43, 1, 17, 26, 15)); int n = arr.size(); System.out.println(findMax(arr, k, n)); }} |
Python3
def findMax(arr, k, n): # initialize two vectors curr and prev to keep # track of only current and previous row of Dp prev = [0] * (k + 1) curr = [0] * (k + 1) # iterative over subproblems and get the current computation for i in range(1, n + 1): # initialize curr vector for j in range(k): curr[j] = prev[j] # get the current value by the help of previous row curr[arr[i - 1] % k] = max(curr[arr[i - 1] % k], arr[i - 1]) for j in range(k): m = (j + arr[i - 1]) % k if prev[j] != 0: curr[m] = max(curr[m], arr[i - 1] + prev[j]) # assigning curr to prev for further iteration prev = curr.copy() # print result return curr[0]# Driver codek = 16arr = [43, 1, 17, 26, 15]n = len(arr)print(findMax(arr, k, n)) |
C#
using System;using System.Collections.Generic;class GFG { // Function to return the maximum sum // divisible by k from elements of v static int findMax(List<int> arr, int k, int n) { // initialize two vectors curr and prev to keep // track of only current and previous row of Dp List<int> prev = new List<int>(new int[k + 1]); List<int> curr = new List<int>(new int[k + 1]); // iterative over subproblems and get the current // computation for (int i = 1; i <= n; i++) { // initialize curr vector for (int j = 0; j < k; j++) { curr[j] = prev[j]; } // get the current value by the help of previous // row curr[arr[i - 1] % k] = Math.Max( curr[arr[i - 1] % k], arr[i - 1]); for (int j = 0; j < k; j++) { int m = (j + arr[i - 1]) % k; if (prev[j] != 0) curr[m] = Math.Max( curr[m], arr[i - 1] + prev[j]); } // assigning curr to prev for further iteration prev = new List<int>(curr); } // print result return curr[0]; } // Driver code static void Main() { int k = 16; List<int> arr = new List<int>{ 43, 1, 17, 26, 15 }; int n = arr.Count; Console.WriteLine(findMax(arr, k, n)); }} |
Javascript
// Function to return the maximum sum// divisible by k from elements of vfunction findMax(arr, k, n) { // initialize two arrays curr and prev to keep // track of only current and previous row of Dp let prev = new Array(k + 1).fill(0); let curr = new Array(k + 1).fill(0); // iterate over subproblems and get the current computation for (let i = 1; i <= n; i++) { // initialize curr array for (let j = 0; j < k; j++) { curr[j] = prev[j]; } // get the current value by the help of previous row curr[arr[i - 1] % k] = Math.max(curr[arr[i - 1] % k], arr[i - 1]); for (let j = 0; j < k; j++) { let m = (j + arr[i - 1]) % k; if (prev[j] != 0) curr[m] = Math.max(curr[m], arr[i - 1] + prev[j]); } // assigning curr to prev for further iteration prev = [...curr]; } // print result return curr[0];}// Driver codelet k = 16;let arr = [43, 1, 17, 26, 15];let n = arr.length;console.log(findMax(arr, k, n)); |
Output
32
Time Complexity: O(N*K)
Auxiliary Space: O(K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
