Code

Python

import heapq
def canDistributeWithCapacity(gameSize, k, capacity):
    # We use a max-heap to track games sorted by size    gameSize.sort()  # Sort in increasing order to easily pair largest with smallest    i, j = 0, len(gameSize) - 1  # Two pointers, smallest (i) and largest (j)    pen_drive_count = 0    while i <= j:
        if gameSize[j] > capacity:
            # If the largest game itself exceeds the capacity, we cannot distribute            return False        if gameSize[i] + gameSize[j] <= capacity:
            # If smallest + largest game can fit, pair them            i += 1  # Use the smallest game        # Always use the largest game        j -= 1        pen_drive_count += 1    return pen_drive_count <= k
def getMinStorageCapacity(gameSize, k):
    left, right = max(gameSize), sum(gameSize)  # Binary search bounds    while left < right:
        mid = (left + right) // 2        if canDistributeWithCapacity(gameSize, k, mid):
            right = mid  # Try a smaller capacity        else:
            left = mid + 1  # Increase the capacity    return left  # The smallest capacity that works# Example usagen = 4gameSize = [9, 2, 4, 6]
k = 3print(getMinStorageCapacity(gameSize, k))  # Output should be 9

C++

#include <iostream>#include <vector>#include <algorithm>using namespace std;// TODO:// 1. Sort the game sizes array.// 2. Use binary search to find the minimum pen drive capacity.// 3. For each capacity, use a greedy approach with two pointers (left, right) to assign games to pen drives.// 4. Try to fit the largest (right pointer) and the smallest (left pointer) game in one pen drive.//    - If they fit, move both pointers.//    - If they don't fit, move only the right pointer.// 5. Return the smallest capacity where all games fit within `k` pen drives.bool canDistributeWithCapacity(const vector<int>& gameSize, int k, int capacity) {    int i = 0, j = gameSize.size() - 1;    int penDriveCount = 0;    while (i <= j) {        // If the largest game itself is too large for the capacity, return false.        if (gameSize[j] > capacity) return false;        // Try to pair the smallest and largest game.        if (gameSize[i] + gameSize[j] <= capacity) {            ++i;  // Move left pointer when we fit two games in one pen drive.        }        // Move right pointer to place the largest game in a pen drive.        --j;        ++penDriveCount;  // We've used one pen drive.    }    // Check if we used too many pen drives.    return penDriveCount <= k;}int getMinStorageCapacity(vector<int>& gameSize, int k) {    // Sort game sizes in increasing order.    sort(gameSize.begin(), gameSize.end());    // Binary search for the minimum possible capacity.    int left = *max_element(gameSize.begin(), gameSize.end());  // The capacity can't be smaller than the largest game.    int right = accumulate(gameSize.begin(), gameSize.end(), 0);  // Maximum possible capacity is sum of all game sizes.    while (left < right) {        int mid = (left + right) / 2;        if (canDistributeWithCapacity(gameSize, k, mid)) {            right = mid;  // Try for a smaller capacity.        } else {            left = mid + 1;  // Increase capacity if mid is insufficient.        }    }    // The smallest capacity where all games fit within k pen drives.    return left;}

Comments

Sort the array and binary search for the answer, greedily assigning 2 games (one large, one small) into a pen drive whenever possible.

Start with a pointer at the right end of the array and another at the left end. If the sum of right and left values is within pen drive size, pair them and move both pointers. Otherwise select only the right element and move the right pointer. Why this is optimal: If the largest element cannot pair with the smallest element, nothing else can. If something else pairs with it, we can swap them (exchange argument) and get a solution that is at least as optimal.

Binary search for the pen drive size and use the above method to check if it is enough.