Last Updated: 27 Nov, 2020
Chocolate Fest
Moderate
Asked in companies
Alex is taking part in a chocolate eating competition. There are ‘N’ boxes of chocolate numbered ‘0’ to ‘N - 1’. Each box contains some chocolates. The boxes are arranged in a line, with the box ‘0’ being the nearest to Alex. To win, Alex has to eat more than ‘X’ number of chocolates using minimum boxes. Alex can only eat chocolates from contiguous boxes. That is, he can choose some i and j (i <= j) and eat all the chocolates from box i, box i + 1, ..., box j. Alex is lazy, so if there are many optimal choices, he will choose the boxes nearest to him.
Given an array ‘choco’ containing the number of chocolates in each box, predict the boxes that Alex will choose. It is guaranteed that one such choice always exists.
Input Format:
The first line contains ‘T’, denoting the number of test cases.
The first line of each test case contains two integers, ‘N’ and ‘X’, denoting the number of boxes and the target, respectively.
The second line of each test case contains an array ‘choco’ of ‘N’ space separated integers, denoting the number of chocolates in each box.
Output Format:
For each test case, print an array of integers denoting the number of chocolates in the boxes that Alex will pick.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 5
1 <= N <= 10^5
1 <= X <= 10^9
1<= choco[i] <= 10^4
Where ‘T’ is the number of test cases, ‘N’ is the number of boxes, ‘X’ is the target, and ‘choco[i]’ is the number of chocolates in the box ‘i’, where 0 <= i <= N - 1.
Time Limit: 1 sec
Approaches
Since we can choose only contiguous boxes, we can check all the options and find the most optimal solution.
The steps are as follows:
- Initialize min_length as ‘N’, denoting the minimum boxes to get the sum of chocolates more than ‘X’.
- Initialize starting_index as 0.
- Traverse the array from i = 0 to i = N - 1, denoting the starting position of the choice.
- Initialize curr_sum = 0, denoting the number of chocolates in this choice.
- Traverse the array from j = i to j = N - 1, denoting the ending position of the choice.
- Add arr[j] to curr_sum, so that it contains the sum of chocolates from box i to box j.
- If the sum of chocolates is more than X and the number of boxes is less than min_length, update min_length and store starting_index as i.
- Now we have a starting index signifying the starting index for the optimal choice and min_length. So, we insert the number of chocolates from box starting_index to starting_index + min_length and return the array.
The main idea here is that if an array has a sum of chocolates less than ‘X’, it is useless to check any of its subarrays. We increase the end index one by one. And accordingly, reduce the starting index to have the smallest subarray with sum more than ‘X’. When we increase the ending index, the current sum increases. Now it is only beneficial to decrease the starting index or keep it the same.
The steps are as follows:
- We initialize the starting index of result ‘start_index’ as 0, the current sum of chocolates ‘curr_sum’ as 0, and the minimum length of optimal solution ‘min_len’ as n + 1.
- We initialize both the current starting index ‘start’ and the current ending index ‘end’ as 0.
- We traverse while ‘end’ is less than N.
- We increase ‘end’ while curr_sum is less than or equal to X and ‘end’ is less than N.
- We now increase start while curr_sum is greater than X and start is less than N.
- If the current length of the subarray (end - start) is less than min_length, we update min_length and also update start_index as ‘i’.
- Now we have start_index signifying the starting index for the optimal choice and min_length. So, we insert the number of chocolates from box start_index to start_index + min_length and return the array.
Similar problems