COIN DIVISION

CONCEPTS USED:

Dynamic programming.

DIFFICULTY LEVEL:

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.

[TABS_R id=2164]
[forminator_quiz id=”2165″]
*Space complexity- O(NN).**

Previous post DROP EGG
Next post LONGEST COMMON SUBSEQUENCE

Leave a Reply

Your email address will not be published. Required fields are marked *