[Solved] Book Fair with Java, C++, Python

Book Fair: Eggsy and Hary, two friends have pooled up all the old books they have and are selling them in the town book fair. Each book has a certain price they want to sell it on. To encourage the sale, they have put an offer. If a person buys one book, they will be given a certain number of extra books from the pile of the person’s choosing, for free. If the number of books left in the pile is less than the decided number of extra books, the person will be given all the remaining books for free.

Eggsy and Hary want to know what is the maximum money they can get from this offer if all the books are sold, and also the minimum money. You need to help them find that.

Input Format

The first line of input is an integer n, denoting the number of books in Eggsy and Hary’s pile.

The second line of input contains n space separated integers p1, p2, … pn, each denoting the price of n respective books.

The third line of input contains an integer extra_books, denoting the number of extra books given for free for each book purchase.

Constraints

1 <= n < 106

1 <= pi < 107 for all 1 <= i <= n

1 <= extra_books < 105

Output Format

The output will be two lines, each containing a single integer.

The integer in first line will denote the minimum money that Eggsy and Hary can get from selling all the books under the offer.

The integer in second line will denote the maximum money that Eggsy and Hary can get from selling all the books under the offer.

Sample Input :

5

67 22 35 43 11

2

Sample Output :

33

110

Explanation

Consider a case, where a person comes and buys the book with price 11. And then he picks the books with price 43 and 67 for free. Another person comes and picks the book with price 22. At this point, the only book left is the book with price 35. That is taken by her for free.

The total money that Eggsy and Hary get in this case is 11 + 22 = 33. This is also the minimum money they can get in any combination of sale.

Now, consider the case where a person comes and buys the book with price 67. And then he picks the books with price 11 and 22 for free. Another person comes and picks the book with price 43 and the book with price 35 is taken by her for free.

The total money that Eggsy and Hary get in this case is 67 + 43 = 110. This is also the maximum money they can get in any combination of sale.

Hence the results 33 and 110.

Sample Input :

2

100 200

1

Sample Output :

100 200

Explanation

Since only 1 extra book if allowed for free, therefore the best case in terms of money is if a person buys the book with price 200 and takes the other one for free. The worst case in terms of money will be if a person buys the book with price 100 and takes the other one for free. Hence the minimum and maximum money will be 100 and 200 respectively.

Solution

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int extra = sc.nextInt();
        Arrays.sort(arr);
        int min = 0;
        int max = 0;
        int i = 0;
        int j = n-1;
        while(i<=j){
            min += arr[i];
            i++;
            j -= extra;
        }
        i = 0;
        j = n-1;
        while(i<=j){
            max += arr[j];
            j--;
            i += extra;
            // sauravhathi
        }
        System.out.println(min);
        System.out.println(max);
    }
}

// c++
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    int extra;
    cin >> extra;
    sort(arr, arr+n);
    int min = 0;
    int max = 0;
    int i = 0;
    int j = n-1;
    while(i<=j){
        min += arr[i];
        i++;
        j -= extra;
        // sauravhathi
    }
    i = 0;
    j = n-1;
    while(i<=j){
        max += arr[j];
        j--;
        i += extra;
    }
    cout << min << endl;
    cout << max << endl;
}

# Python
n = int(input())
arr = list(map(int, input().split()))
extra = int(input())
arr.sort()
min = 0
max = 0
i = 0
j = n-1
while i<=j:
    min += arr[i]
    i += 1
    j -= extra
    # sauravhathi
i = 0
j = n-1
while i<=j:
    max += arr[j]
    j -= 1
    i += extra
print(min)
print(max)

Happy Learning – If you require any further information, feel free to contact me.