Virtu: Heaviest Plate Subset Within a Barbell Capacity, Up to 42 Plates

Quick Overview

Choose a subset of up to 42 barbell plates, each used at most once, so the total weight is as large as possible without exceeding the barbell's capacity. Tests picking an approach that fits a small plate count but weights and a capacity of up to one billion.

Heaviest Plate Subset Within a Barbell Capacity, Up to 42 Plates

Company: Virtu

Role: Quantitative Researcher

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Online Assessment

You have `n` barbell plates with weights `weights[0], ..., weights[n - 1]`, and a barbell that can hold a total weight of at most `max_capacity`. Choose a subset of the plates, using each plate at most once, whose total weight is as large as possible without exceeding `max_capacity`. Return that maximum total weight. ### Function Signature ```python def max_lift(weights: list[int], max_capacity: int) -> int: ``` ### Rules - The empty subset is allowed, so the answer is `0` when every plate is heavier than `max_capacity`. - Plates with equal weights are distinct plates, and each one may be used at most once. - Return only the maximum total weight, not the chosen plates. ### Constraints - `1 <= n <= 42`, where `n = len(weights)` - `1 <= max_capacity <= 10^9` - `1 <= weights[i] <= 10^9` - The total of all weights can reach `4.2 * 10^10`, which exceeds `2^31 - 1`, so use 64-bit integers for sums. All sums stay far below `2^53`. ### Examples **Example 1** ```text Input: weights = [7, 1, 5, 6, 2], max_capacity = 7 Output: 7 ``` For example, the plate of weight `7` alone, or the plates `1` and `6`, or `5` and `2`, reach the capacity exactly. **Example 2** ```text Input: weights = [4, 8, 9], max_capacity = 16 Output: 13 ``` The plates `8` and `9` total `17`, which is too heavy. The best feasible subset is `4` and `9`. **Example 3** ```text Input: weights = [10, 20, 30], max_capacity = 5 Output: 0 ``` Every plate exceeds the capacity, so only the empty subset fits.

Overview: Choose a subset of up to 42 barbell plates, each used at most once, so the total weight is as large as possible without exceeding the barbell's capacity. Tests picking an approach that fits a small plate count but weights and a capacity of up to one billion.

You have `n` barbell plates with weights `weights[0], ..., weights[n - 1]`, and a barbell that can hold a total weight of at most `max_capacity`. Choose a subset of the plates, using each plate at most once, whose total weight is as large as possible without exceeding `max_capacity`. Return that maximum total weight. ### Rules - The empty subset is allowed, so the answer is `0` when every plate is heavier than `max_capacity`. - Plates with equal weights are distinct plates, and each one may be used at most once. - Return only the maximum total weight (a single integer), not the chosen plates. Several different subsets may reach the same maximum; the answer is that total. ### Constraints - `1 <= n <= 42`, where `n = len(weights)` - `1 <= max_capacity <= 10^9` - `1 <= weights[i] <= 10^9` - The total of all weights can reach `4.2 * 10^10`, which exceeds `2^31 - 1`, so use 64-bit integers for sums (Java `long`, C++ `long long`). All sums stay far below `2^53`. ### Example 1 Input: `weights = [7, 1, 5, 6, 2]`, `max_capacity = 7` Output: `7` The plate of weight `7` alone, or the plates `1` and `6`, or `5` and `2`, reach the capacity exactly. ### Example 2 Input: `weights = [4, 8, 9]`, `max_capacity = 16` Output: `13` The plates `8` and `9` total `17`, which is too heavy. The best feasible subset is `4` and `9`.

Constraints

1 <= n <= 42, where n = len(weights)
1 <= max_capacity <= 10^9
1 <= weights[i] <= 10^9
The total of all weights can reach 4.2 * 10^10, which exceeds 2^31 - 1, so use 64-bit integers for sums (Java long, C++ long long). All sums stay far below 2^53.

Examples

Input: ([7, 1, 5, 6, 2], 7)

Expected Output: 7

Explanation: Source example 1: several tied subsets (7, 1+6, 5+2) reach the capacity exactly; a strict < check would give 6.

Input: ([4, 8, 9], 16)

Expected Output: 13

Explanation: Source example 2: 8+9=17 is too heavy, so the best is 4+9; smallest-first greedy stops at 12.

Hints

n is at most 42 while the weights and the capacity reach 10^9: let the small bound on the number of plates, not the size of the numbers, drive your approach.
Every plate is positive, so once a partial selection is heavier than max_capacity, adding more plates can never make it feasible again.
Sums of only a few plates can exceed 2^31 - 1, so keep every total in a 64-bit integer.

Approach

Meet in the middle. If the total of all plates fits, return it directly. Otherwise split the plates by position into two halves of at most 21 plates each and list every subset sum of each half that does not exceed max_capacity. Because every plate is positive, a partial sum above the capacity can never become feasible again, so such sums (and any single plate heavier than the capacity) are dropped without losing an answer. Sort the distinct sums of the second half. For each first-half sum s, binary-search the largest second-half sum that is at most max_capacity - s; it always exists because the empty subset contributes 0. Every subset of all plates is exactly one pair (subset of the first half, subset of the second half), and the pair is feasible exactly when the two sums add to at most max_capacity, so the maximum of s plus its best partner over all s is the answer. The search stops early once that maximum equals max_capacity, since nothing can exceed it. Edge cases: n = 1 (the first half is empty and contributes only 0), every plate heavier than the capacity (only the empty subset remains, answer 0), duplicate weights (subsets are enumerated by position, so each plate is used at most once), and totals above 2^31 - 1 (all arithmetic is 64-bit; in JavaScript every sum stays below 2^53).

Time complexity:

O(2^(n/2) * n)

Space complexity:

O(2^(n/2))