I came across the following problem on Hackerrank.com. The solution is provided for the same.
Problem :
You and your K-1 friends want to buy N flowers. Flower number i has cost ci. Unfortunately the seller does not like a customer to buy a lot of flowers, so he tries to change the price of flowers for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*ci dollars to buy flower number i.
You and your K-1 firends want to buy all N flowers in such a way that you spend the as few money as possible.
Input:
The first line of input contains two integers N and K.
next line contains N positive integers c1,c2,…,cN respectively.
Output:
Print the minimum amount of money you (and your friends) have to pay in order to buy all n flowers.
Sample input :
3 3
2 5 6
Sample output :
13
Explanation :
In the example each of you and your friends should buy one flower. in this case you have to pay 13 dollars.
Constraint :
1 <= N, K <= 100
Each ci is not more than 1000,000
Solution :
import java.util.Scanner;
public class Flowers {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N, K;
N = in.nextInt();
K = in.nextInt();
int C[] = new int[N];
for(int i=0; i<N; i++){
C[i] = in.nextInt();
}
MergeSort(C, 0, C.length-1);
int q=0;
int cost=0;
for(int i=0; i<C.length;i++){
q=i/K;
cost+=(q+1)*C[i];
}
System.out.println(cost);
}
private static void MergeSort(int[] myArray, int p, int r) {
if(p<r){
int q=(p+r)/2;
MergeSort(myArray, p, q);
MergeSort(myArray, q+1, r);
Merge(myArray, p, q, r);
}
}
private static void Merge(int[] myArray, int p, int q, int r) {
int n1=q-p+1;
int n2=r-q;
int L[]=new int[n1];
int R[]=new int[n2];
for(int i=0; i<L.length;i++){
L[i]=myArray[p+i];
}
for(int j=0; j<R.length; j++){
R[j]=myArray[q+j+1];
}
int i=0,j=0;
for(int k=p; k<=r;k++){
if(i>=L.length){
myArray[k]=R[j];
j++;
}else if(j>=R.length){
myArray[k]=L[i];
i++;
}else if(L[i]>R[j]){
myArray[k]=L[i];
i++;
}else{
myArray[k]=R[j];
j++;
}
}
}
}
Problem :
You and your K-1 friends want to buy N flowers. Flower number i has cost ci. Unfortunately the seller does not like a customer to buy a lot of flowers, so he tries to change the price of flowers for customer who had bought flowers before. More precisely if a customer has already bought x flowers, he should pay (x+1)*ci dollars to buy flower number i.
You and your K-1 firends want to buy all N flowers in such a way that you spend the as few money as possible.
Input:
The first line of input contains two integers N and K.
next line contains N positive integers c1,c2,…,cN respectively.
Output:
Print the minimum amount of money you (and your friends) have to pay in order to buy all n flowers.
Sample input :
3 3
2 5 6
Sample output :
13
Explanation :
In the example each of you and your friends should buy one flower. in this case you have to pay 13 dollars.
Constraint :
1 <= N, K <= 100
Each ci is not more than 1000,000
Solution :
import java.util.Scanner;
public class Flowers {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N, K;
N = in.nextInt();
K = in.nextInt();
int C[] = new int[N];
for(int i=0; i<N; i++){
C[i] = in.nextInt();
}
MergeSort(C, 0, C.length-1);
int q=0;
int cost=0;
for(int i=0; i<C.length;i++){
q=i/K;
cost+=(q+1)*C[i];
}
System.out.println(cost);
}
private static void MergeSort(int[] myArray, int p, int r) {
if(p<r){
int q=(p+r)/2;
MergeSort(myArray, p, q);
MergeSort(myArray, q+1, r);
Merge(myArray, p, q, r);
}
}
private static void Merge(int[] myArray, int p, int q, int r) {
int n1=q-p+1;
int n2=r-q;
int L[]=new int[n1];
int R[]=new int[n2];
for(int i=0; i<L.length;i++){
L[i]=myArray[p+i];
}
for(int j=0; j<R.length; j++){
R[j]=myArray[q+j+1];
}
int i=0,j=0;
for(int k=p; k<=r;k++){
if(i>=L.length){
myArray[k]=R[j];
j++;
}else if(j>=R.length){
myArray[k]=L[i];
i++;
}else if(L[i]>R[j]){
myArray[k]=L[i];
i++;
}else{
myArray[k]=R[j];
j++;
}
}
}
}