Minimize Array Sum Using Divisible Replacements - Solution & Explanation

Problem Overview: You are given an integer array and allowed to repeatedly replace a number if it is divisible by another number in the array. The replacement typically reduces the value (for example replacing a number with the quotient after division). The goal is to perform these divisible replacements strategically so the final sum of the array is as small as possible.

Approach 1: Brute Force Pair Simulation (O(n^2 log n) time, O(1) space)

Check every pair (i, j) and see whether nums[i] % nums[j] == 0. If the condition holds, simulate replacing nums[i] with the smaller value produced by the division. After each modification, recompute possible pairs and continue until no further reduction is possible. This method literally simulates all valid operations and repeatedly scans the array to find reductions. It works for small inputs but becomes slow because every iteration requires checking all pairs again.

Approach 2: Greedy with Sorting (O(n log n) time, O(1) space)

Sort the array so smaller values appear first. Smaller numbers are more likely to divide larger numbers, which means they can create larger reductions in the total sum. Iterate from the smallest element and attempt to reduce larger elements whenever the divisibility condition holds. Sorting ensures that when you evaluate nums[i], all potential divisors before it are already minimal candidates. This greedy ordering significantly cuts down redundant checks compared to the brute force approach.

Approach 3: Greedy + Min Heap Reduction (O(n log n) time, O(n) space)

Push all values into a min heap. The smallest element becomes the most useful divisor because it can potentially reduce many larger elements. Repeatedly pop the smallest value and attempt to reduce other elements that are divisible by it. When a reduction occurs, push the new value back into the heap so it can participate in future operations. The heap structure ensures you always process the smallest divisor first, which tends to minimize the total sum quickly.

Recommended for interviews: The greedy strategy combined with sorting or a heap is what interviewers typically expect. Starting with the brute force pair check shows you understand the divisibility relationship between elements. Transitioning to a greedy strategy demonstrates algorithmic insight and reduces the complexity to roughly O(n log n). Concepts here overlap with greedy algorithms, heap / priority queue, and basic array processing.