Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Chocolates

Last Updated on March 28, 2022 by Ria Pathak

Sorting

Medium

Problem Statement (Simplified):

For given values of `N` and `K`, an array of `N` elements is given. You can pick at most `K` items in one turn, each turn costs you (`turn number` * `element value`). For all values `i` between 1 and `N`, calculate the minimum possible value of picking exactly `i` items.

Test Case

``````Input:
1
5 2
4 5 3 7 5

Output:
3 7 15 24 39

Explanation:
For K=4,
We can select 3, 4, 5, and 5. As our daily limit is 2, so we split chocolates in 2 days, we'll select larger chocolates for day 1 and select rest for day 2. So we can select chocolates like:
1st Day = 5 and 5
2nd Day = 3 and 4

So, its cost will be 1(5)+1(5)+2(3)+2(4), so our final cost becomes 24. Hence, for K=4 we print 24.``````

See original problem statement here

Solving Approach :

1) If we sort the provided array, it would be easy to pick items, as we can pick elements from the start of the array and the total cost would be minimal.
2) We can use Cummulative Array to solve this problem.
Cummulative Array: Cummulative Array is an array that contains the sum of all elements before the current index and element at the current index.
3) For any value between K, the minimum cost will be the sum of the current index. But if maximum capacity i.e. `M` reaches or is crossed, it also includes cost at (current day – capacity)th day.

Examples

Let array `A` be,

Graphic-1 Here

`size` of array is `5` and we have capacity of `2`.

We arrange array in non-decreasing order. So array `A` becomes,

Graphic-2 Here

We create a cummulative array from our array `A`, hence our array `A` becomes,

Graphic-3 Here

For any value between `1` and `size`, for e.g. `4`, it will represent index `3` in our array, as value is greater than our capacity, so minimum cost will be,

minimumCost = currentDayCost + (currentDay – capacity)th Day cost
minimumCost = 18 + (4-3)th day cost
minimumCost = 18 + A[1]
minimumCost = 18 + 7
minimumCost = 25,

Hence, `minimumCost` will be `25` for the index `3`, hence we get values for all days like this.

Solutions

```#include <stdio.h>

void merge(long long arr[], int start, int mid, int end){
long long left[mid-start+1];
long long right[end-mid];

for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(long long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main()
{
int test;
scanf("%d",&test);

while(test--){

int n, k;
scanf("%d%d",&n,&k);

long long int chocolate[n];
for(int i=0; i<n; i++)
scanf("%lld",&chocolate[i]);

mergeSort(chocolate, 0, n-1);

for(int i=1; i<n; i++)
chocolate[i] += chocolate[i-1];

for(int i=0; i<n; i++){
if(i>=k)
chocolate[i] += chocolate[i-k];
printf("%lld ",chocolate[i]);
}

printf("\n");

}
}
```
```#include <bits/stdc++.h>
using namespace std;

void merge(long long arr[], int start, int mid, int end){
long long left[mid-start+1]={0};
long long right[end-mid]={0};
for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

void mergeSort(long long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

int main()
{
int test;
cin>>test;

while(test--){

int n, k;
cin>>n>>k;

long long int chocolate[n];
for(int i=0; i<n; i++)
cin>>chocolate[i];

mergeSort(chocolate, 0, n-1);

for(int i=1; i<n; i++)
chocolate[i] += chocolate[i-1];

for(int i=0; i<n; i++){
if(i>=k)
chocolate[i] += chocolate[i-k];
cout<<chocolate[i]<<" ";
}

cout<<endl;

}
}
```
```import java.util.*;
import java.io.*;

public class Main {

static void merge(long arr[], int start, int mid, int end){
long left[] = new long[mid-start+1];
long right[] = new long[end-mid];

for(int i=start; i<mid+1; i++){
left[i-start] =  arr[i];
}
for(int i=mid+1; i<=end; i++){
right[i-(mid+1)] = arr[i];
}
int leftIndex=0, rightIndex=0, arrIndex=start;
for( ; leftIndex<=mid-start && rightIndex<end-mid; arrIndex++){
if(left[leftIndex]<right[rightIndex]){
arr[arrIndex] = left[leftIndex++];
}
else{
arr[arrIndex] = right[rightIndex++];
}
}

while(leftIndex<=mid-start){
arr[arrIndex++] = left[leftIndex++];
}

while(rightIndex<end-mid){
arr[arrIndex++] = right[rightIndex++];
}

}

static void mergeSort(long arr[], int start, int end){
if(end==start)
return;
mergeSort(arr,start,(start+end)/2);
mergeSort(arr,((start+end)/2)+1,end);
merge(arr,start,(start+end)/2,end);
}

public static void main(String args[]) throws IOException {

while(test-->0){

String[] s1 = s.split(" ");
int n = Integer.parseInt(s1[0]);
int k = Integer.parseInt(s1[1]);

long chocolate[] = new long[n];
String s2[] = s.split(" ");
for(int i=0; i<n; i++)
chocolate[i] = Long.parseLong(s2[i]);

mergeSort(chocolate, 0, n-1);

for(int i=1; i<n; i++)
chocolate[i] += chocolate[i-1];

for(int i=0; i<n; i++){
if(i>=k)
chocolate[i] += chocolate[i-k];
System.out.print(chocolate[i]+" ");
}

System.out.println();

}
br.close();
}
}
```

Space Complexity: O(`1`)

[forminator_quiz id="1207"]

This article tried to discuss Sorting. Hope this blog helps you understand and solve the problem. To practice more problems on Sorting you can check out MYCODE | Competitive Programming.