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:

Since we are using a recursive function and in the worst case we are making two recursive calls at each step and so, the time complexity will be O(2^N).

For the SECOND subproblem:

Since we are using a nested loop to traverse through each subarray and so, the time complexity will be O(N^2).

For the THIRD subproblem:

Since we are using the segment tree technique which will take O(log(N)) time for query and update and O(N*log(N)) time for build and so, the time complexity will be O((N+Q)*log(N)).

For the FIRST subproblem:

Since the height of the recursion tree can go up to ‘N’ in the worst case and so, the space complexity will be O(N).

For the SECOND subproblem:

Since we are not using any extra space and so, the space complexity will be O(1).

For the THIRD subproblem:

Since we are using the segment tree technique which occupies O(N) space for segment tree array and O(log(N)) space for recursive build function and so, the space complexity will be O(N*log(N)).