Maximize the Bottom-Half Warehouse Loads - Amazon Intern Online Assessment questions IIT BHU

Problem Preview

"You are given an array `loads` of length `N`, where `loads[i]` denotes the number of pieces in the `i`-th load. You are also given an even integer `K` representing the number of warehouses. Each warehouse can receive pieces from **only one** load, but a load may be **split among multiple warehouses**. After distributing all pieces into exactly `K` warehouses, let `warehouse[i]` denote the total pieces assigned to the `i`-th warehouse. Sort the warehouse loads in non-decreasing order and discard the largest `K/2` warehouse loads. Your task is to **maximize the sum of the remaining `K/2` smallest warehouse loads**. Return the maximum possible value. --- ## Input Format * The first line contains two integers `N` and `K`. * The second line contains `N` integers representing `loads[i]`. --- ## Output Format Print a single integer — the maximum possible sum of the smallest `K/2` warehouse loads after an optimal distribution. --- ## Constraints * `1 ≤ N ≤ 2 × 10^5` * `2 ≤ K ≤ 2 × 10^5` * `K` is even. * `1 ≤ loads[i] ≤ 10^9` * Every warehouse must receive a non-negative number of pieces. * Every warehouse receives pieces from exactly one load. * A load may be split across multiple warehouses. --- ## Example 1 ### Input ```text 3 4 8 5 3 ``` ### Output ```text 5 ``` ### Explanation One optimal distribution is: * Load 8 → `3, 5` * Load 5 → `5` * Load 3 → `3` Warehouse loads become: ```text 3 3 5 5 ``` After sorting: ```text 3 3 5 5 ``` Discard the largest `2` warehouses: ```text 5 5 ``` Remaining sum: ```text 3 + 3 = 6 ``` Thus, the maximum possible answer is `6`. --- ## Example 2 ### Input ```text 2 2 10 6 ``` ### Output ```text 6 ``` ### Explanation Assign one load to each warehouse: ```text 10 6 ``` After sorting: ```text 6 10 ``` Discard the largest warehouse (`10`). Remaining sum is: ```text 6 ``` Hence, the answer is `6`."