Boxes and chocolates

The first thing that we have to consider is that Kevin will only buy chocolates in the multiple of 3 because he has three children and he wants to distribute chocolates in an equal amount.

For the FIRST subproblem: 

The basic idea is to go through recursively and keep counting the subsequences whose sum is divisible by 3.

We will make a helper function ( named “subsequenceOf3” ) which takes the given boxes, index of a particular box, and the current sum of chocolates as the arguments and returns the maximum number of ways in which Kevin can buy the chocolates if he chooses boxes in random order. Make sure of taking modulo with 10^9 + 7.

int subsequenceOf3 (vector<int> &arr, int ind, int sum)

Where ‘arr' is the given array/boxes, ‘ind’ is the number of boxes left, and ‘sum’ is the sum of chocolates.

The steps are as follows:

1. In the “subsequenceOf3” function
   • if ‘IND’ becomes 0 then return 1 if ‘SUM’+ ‘ARR’[ i ] is divisible by 3, Otherwise return 0.
   • If, ‘SUM’ + ‘ARR[ IND ]’ is divisible by 3 then return 1 + two function calls with arguments as ('ARR', ‘IND’ - 1, ‘SUM’) and ('ARR', ‘IND’ - 1, ‘SUM’ + ‘ARR’[ i ]) by taking modulo with 10^9+7.
   • Else, return the summation of two function calls i.e. subsequenceOf3('ARR', ‘IND’ - 1, ‘SUM’) and subsequenceOf3('ARR', ‘IND’ - 1, ‘SUM’ + ‘ARR[ IND ]') by taking modulo with 10^9+7.
2. In the given function just call the “subsequenceOf3” function.

For the SECOND subproblem:

The basic idea is to traverse through all the subarrays using a nested loop and increment the counter if the sum of the elements of a particular subarray is a multiple of 3.

We are going to use an additional function (named “subarrayOf3”) which takes boxes as the input and returns the maximum number of ways in which Kevin can buy the chocolates if he can only choose consecutive boxes.

int subarrayOf3(vector<int> &arr, int N)

Where ‘ARR’ is the given array/boxes and ‘N’ is the total number of boxes.

The steps are as follows:

1. In the “subarrayOf3” function
   • Create a variable ‘COUNT’ to store the count of subarrays whose sum is the multiple of 3. Initialize ‘COUNT’ with 0.
   • Iterate through ‘ARR’ (say, iterator = ‘i’)
     • Create another variable ‘SUM’ to store the sum of elements and initialize it with 0.
     • Iterate through ‘ARR’ again but from ‘i’ to ‘N’ - 1. (say, iterator = ‘j’)
       • Add ‘ARR[ j ]’ to sum and check if the sum is now a multiple of 3 then increment the ‘COUNT’ by 1.
   • Return ‘COUNT’.
2. In the given function call “subarrayOf3”.

For the THIRD subproblem:

The basic idea is to use a segment tree to find the maximum number of ways in which Kevin can buy the chocolates within a range ['L', ‘R’] (inclusive) if he chooses boxes in any order (means we have to find the number of subsequences having sum divisible by 3). We will store three integer variables at each node by using struct (in case of CPP):

struct node { 

int rem0 ( it stores the frequency of numbers having remainder 0 when divided by 3).

int rem1 ( it stores the frequency of numbers having remainder 1 when divided by 3).

int rem2 ( it stores the frequency of numbers having remainder 2 when divided by 3).

}

For Reference: https://cp-algorithms.com/data_structures/segment_tree.html

And, the merge function (receives two nodes n1 and n2) is used to find the merged node which computes new rem0, rem1, and rem2 by taking modulo with 10^9+7 as:

new rem0 = ((n1.rem0 * n2.rem0)%mod + (n1.rem1 * n2.rem2)%mod + (n1.rem2 * n2.rem1)%mod + n1.rem0 + n2.rem0)%mod

new rem1 =  ((n1.rem0 * n2.rem1)%mod + (n1.rem1 * n2.rem0)%mod + n1.rem1 + n2.rem1 + (n1.rem2 * n2.rem2)%mod)%mod

new rem2  = ((n1.rem0 * n2.rem2)%mod + (n1.rem2 * n2.rem0)%mod + n1.rem2 + n2.rem2 + (n1.rem1 * n2.rem1)%mod)%mod

Where ‘mod’ is equal to 10^9+7.

The steps are as  follows:

1. Make a merge function as described above that must return a merged node.
2. Make a build function that will build the segment tree from 0 to ‘N’ - 1 and at each node, it must store ‘REM0’, ‘REM1’, and ‘REM2’.
3. Make an update function that will be used to update the segments of the segment tree that affect due to the change in the value of ‘ARR[ i ]’.
4. Make a query function and code as
   • Check if the segment range is out of the query range then create a struct of type node (which contains  ‘REM0’, ‘REM1’, and ‘REM2’) and return it.
   • Check if the segment range is completely inside the query range then directly return the current node of the segment tree.
   • Compute mid-value of segment range.
   • Call the query function for the left of the segment tree and right of the segment tree and store the obtained result in two variables.
   • Merge the above-obtained result and then return it.
5. In the given function
   • Create a vector named ‘ST’ of type ‘NODE’ that represents the segment tree.
   • Call the build function.
   • Call the update and query function for the respective type of queries.
   • Store the result of each range query in a vector.
   • Return the result of all the subproblems after storing them in a vector of vectors.

For the FIRST subproblem: 

The basic idea is to reduce the time complexity by using Dynamic Programming which will cut down the repeated recursive calls that were taking too much time in the recursive approach (discussed in approach 1).

We will create a ‘DP’ table of size ‘N’*3, where ‘DP’[ i ][ j ] = the number of subsequences of ‘ARR’[ 0...i ] with remainder equal to j and we will compute the value of ‘DP’ for all 0 <= ‘i’ < ‘N’ and 0 <= ‘j’ < 3. A row represents the box counts and a column represents the remainder when the sum of a subsequence is divided by 3.

We will make a helper function ( named “subsequenceOf3” ) to solve this subproblem.

int subsequenceOf3 (vector<int> &arr)

Where ‘arr' is the given array/boxes.

The steps are as follows:

1. In the “subsequenceOf3” function
   • Set 0 for every ‘DP’[ i ][ j ].
   • Make ‘DP’[ 0 ][ ‘ARR’[ 0 ] % 3] = 1 (for the first element of the array), this done because the rest ‘DP’ will be filled by using the values stored in the previous row.
   • Iterate through the ‘ARR’ from 1 to ‘N’ - 1. (say, iterator = ‘i’)
     • Make a temporary array ‘TEMP’ of size 3 store the new counts.
     • For each ‘j’, add the value of ‘ARR’[ i ] with the ‘j’, take modulo 3 and consider it as the new value of ‘j’ and add the result obtained with ‘i’ - 1 in the ‘TEMP’. Make sure of taking modulo with 10^9 + 7.
     • Now, for the box count ‘i’ store the result obtained from the box count ‘i’ - 1 in ‘DP’[ i ][ j ] (for every ‘j’) and add the corresponding value stored in ‘TEMP’. Make sure of taking modulo with 10^9 + 7.
   • Return ‘DP’[ ‘N’ - 1 ][ 0 ].
2. In the given function just call the “subsequenceOf3” function.

For the SECOND subproblem:

The basic idea is to traverse through the array and keep storing the frequency of subarrays as value and the remainder that we get after dividing the sum of this subarray by 3 as key in a HashMap. Add the frequency of subarrays to the counter that gives the pre-stored remainder when divided by 3.

We are going to use an additional function (named “subarrayOf3”)

int subarrayOf3(vector<int> &arr)

Where ‘arr’ is the given array/boxes.

The steps are as follows:

1. In the “subarrayOf3” function
   • Create a variable ‘COUNT’ to store the count of subarrays whose sum is the multiple of 3. Initialize ‘COUNT’ with 0.
   • Create a HaspMap named ‘MP’.
   • Create another variable ‘SUM’ to store the sum of elements and initialize it with 0.
   • Iterate through ‘ARR’. (say, iterator = ‘i’)
     • Add ‘ARR’[ i ] to the ‘SUM’.
     • Check if ‘SUM’ is divisible by 3 then increment the ‘COUNT’ by 1.
     • Store the remainder obtained when we divide ‘SUM’ by 3 in a variable named ‘X’.
     • Check if ‘X’ is already in HashMap then increment ‘COUNT’ by the ‘MP[ X ]’.
     • Increment ‘MP[ X ]’ by 1.
   • Return ‘COUNT’.
2. In the given function call “subarrayOf3”.

For the THIRD subproblem:

The approach for this subproblem is the same as mentioned in “approach 1”.