# COIN DIVISION

#### CONCEPTS USED:

Dynamic programming.

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Arnab is now given N numbers, which are actually stacks of coins containing `a[i]` amount of coins each. Now he is asked to choose any subset of the stacks of coins. But there is a problem Arnab has two brothers and he has to divide the coins equally into three divisions. Find the largest sum of coins which satisfies the above conditions.

#### For Example :

``````1
3
1 4 2

The set {2,4} is the only possible maximum set,
so there are 6 coins which can be divided into three equal groups.``````

#### SOLVING APPROACH:

You are advised to do Maximum Subset Sum using Recursion (if you haven't) first and then come to this problem .

1. You have to find subsets for an array , whose sum is divisible by 3.
2. As there can be many such subsets , print one with maximum sum.

#### You are encouraged to implement the above brute force and think of memoization on your own first ,before looking at the solution.

See original problem statement here

BRUTE FORCE:

Let's define a function `f(i,sum)` where i is the current index and sum ranges from 0 to 2, which is the remainder obtained by dividing it with 3.

For every index i ,`a[i]` will either be included in the sum or not included.

If it is not included,then
increase the index and recur further.

If included, then
`f(i,sum)` will be the maximum of `a[i]` not included and `a[i]`+`solve(i+1,(sum+a[i])%3,v)`.

Brute force approach will take exponential time to calculate the required sum.But if we use recursion with memoization ,we can optimize it using the fundamentals of data structures in c++.

Before proceeding to the solution we can see that the recursive solution will thake exponential time`(`without memoization`)` so we will proceed to the dynamic programming approach.

## Refer to the code for implementation.

``` #include <stdio.h>
int max(int x,int y)
{
if(x>y)return x;
return y;
}
int n;
int dp;
int solve(int i,int sum,int v[]){
if(i==n)return 0;

if(dp[i][sum]!=-1)return dp[i][sum];

int ans=0;
if((sum+solve(i+1,sum,v))%3==0){
ans=solve(i+1,sum,v);
}
if((sum+v[i]+solve(i+1,(sum+v[i])%3,v))%3==0){
ans=max(ans,v[i]+solve(i+1,(sum+v[i])%3,v));
}

return dp[i][sum]=ans;

}

int main()
{

int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++)
scanf("%d",&arr[i]);
memset(dp,-1,sizeof dp);
printf("%d\n",solve(0,0,arr));
}
return 0;
}
```
``` #include <bits/stdc++.h>
using namespace std;
int n;
int dp;
int solve(int i,int sum,int v[]){
if(i==n)return 0;

if(dp[i][sum]!=-1)return dp[i][sum];

int ans=0;
if((sum+solve(i+1,sum,v))%3==0){
ans=solve(i+1,sum,v);
}
if((sum+v[i]+solve(i+1,(sum+v[i])%3,v))%3==0){
ans=max(ans,v[i]+solve(i+1,(sum+v[i])%3,v));
}

return dp[i][sum]=ans;

}

int main()
{

int t;
cin>>t;
while(t--)
{
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
cin>>arr[i];
memset(dp,-1,sizeof dp);
cout<<solve(0,0,arr)<<endl;
}
return 0;
}
```
``` import java.util.*;

class solution{

public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int dp[][]=new int;
int n;
int t=sc.nextInt();
while(t-->0)
{
n=sc.nextInt();

int arr[]=new int[n];

for(int i=0;i<n;i++)
arr[i]=sc.nextInt();

System.out.println(solve(0,0,arr,dp,n));
}
}

static int solve(int i,int sum,int v[],int dp[][],int n){

for(int k=0;k<dp.length;k++){
for(int j=0;j<dp.length;j++){
dp[k][j]=-1;
}
}

if(i==n)
return 0;

if(dp[i][sum]!=-1)
return dp[i][sum];

int ans=0;

if((sum+solve(i+1,sum,v,dp,n))%3==0){
ans=solve(i+1,sum,v,dp,n);
}

if((sum+v[i]+solve(i+1,(sum+v[i])%3,v,dp,n))%3==0){
ans=Math.max(ans,v[i]+solve(i+1,(sum+v[i])%3,v,dp,n));
}

return dp[i][sum]=ans;

}
}
```

*Space complexity- O(NN).**