Interview Questions/Coding/Vault Split Weight Target

Vault Split Weight Target

Preview mode. Log in to edit, run, submit, and save progress.

Hard

Vault Split Weight Target

A secure-logistics firm is dispatching an armored truck from its central vault. The truck's suspension is calibrated for a target load of $T$ kilograms: every kilogram above or below the calibration adds strain on the axles and draws unwanted attention at weigh stations. Inside the vault sit $N$ sealed crates, the $i$-th weighing $W_i$ kilograms. Each crate must be taken whole or not at all, and the dispatcher may load any subset of the crates - including sending the truck out completely empty. If the chosen crates weigh $S$ kilograms in total, the strain of the run is $|S - T|$. Pick the subset that minimizes the strain and report the minimum possible value of $|S - T|$. ### Function Description Complete the function `closestVaultLoad` provided in the editor. The function receives the following parameters:

ParameterTypeDescription
$N$integerthe number of crates in the vault
$T$integerthe truck's calibrated target load
$W$array of integers$W_i$ is the weight of the $i$-th crate

The function must return a single integer - the minimum achievable value of $|S - T|$, where $S$ is the total weight of the loaded subset. ### Input Format - The first line contains two space-separated integers $N$ and $T$. - The second line contains $N$ space-separated integers $W_1, W_2, \ldots, W_N$. ### Output Format Return a single integer: the minimum possible value of $|S - T|$ over all $2^N$ subsets of crates. ### Notes - The empty subset is allowed: an empty truck has $S = 0$ and strain $|0 - T| = T$. - Each crate can be loaded at most once, and crates cannot be split. - Totals can reach $3.8 \times 10^{10}$, so use a 64-bit integer type for sums (`long long` in C++, `long` in Java).

Examples

Example 1
Input:
```text
5 16
7 3 9 12 2
```
Output:
```text

Explanation: Loading the crates weighing $7$ and $9$ gives $S = 7 + 9 = 16$, so the strain is $|16 - 16| = 0$. The target is hit exactly, and $0$ is the best possible answer.

Approach hint

$2^{38}$ subsets is roughly $2.7 \times 10^{11}$ - enumerating them all is far beyond any time limit. But $2^{19}$ is only about half a million. Can you cut the problem in two?

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

Loading...
Input
```text 5 16 7 3 9 12 2 ```
Output
```text