Lock Code Decryption

Hard coding problem: optimizing selection with coprimality constraints

This hard coding problem, asked by a tier-1 quant firm, combines discrete optimization with number-theoretic reasoning. You must find the maximum value of a selected number minus the cost of modifications needed to make that number coprime with all others in an array.

The core challenge is exploring which candidate values to select and, for each candidate, determining the minimum-cost modification set that allows it to be coprime with the rest. Since coprimality depends on greatest common divisors (GCD), you'll need to reason about which elements must be changed to eliminate shared factors with your chosen number. The solution requires balancing the value of the selected number against the cost of forcing coprimality—a classic trade-off in constrained optimization.

• GCD computation and coprimality testing
• Greedy and exhaustive search over candidate selections
• Minimizing modification cost for a fixed candidate
• Handling edge cases (single-element arrays, vacuous coprimality)