LeetCode 3927 - Minimize Array Sum Using Divisible Replacements

The problem gives an integer array nums and allows an operation that can reduce values under a divisibility condition. Specifically, you may choose two indices a and b such that nums[a] % nums[b] == 0, and then replace nums[a] with nums[b].

leetcodemediumarrayhash-tablemathgreedynumber-theory

LeetCode Problem 3927

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Greedy, Number Theory

Solution

Problem Understanding

The problem gives an integer array nums and allows an operation that can reduce values under a divisibility condition. Specifically, you may choose two indices a and b such that nums[a] % nums[b] == 0, and then replace nums[a] with nums[b]. The effect of this operation is that any number in the array can potentially be reduced to a smaller value, but only if that smaller value divides it.

The task is to apply this operation any number of times in any order to minimize the total sum of the array. The output is the minimum possible sum after all optimal replacements.

The key constraint insight is that nums[i] can be as large as 100000 and the array size can also be up to 100000, so an O(n²) simulation is impossible. This strongly suggests that we need a number-theoretic or frequency-based optimization rather than simulating operations.

Edge cases include arrays where no number divides any other number, arrays where all elements are equal, and arrays where a single small value like 1 exists, since 1 can replace every number.

Approaches

Brute Force Approach

A naive approach attempts to repeatedly apply valid operations until no improvement is possible. For every pair (a, b), we check whether nums[a] % nums[b] == 0, and if replacing improves the array, we perform the replacement and repeat until convergence.

This is correct because it directly simulates the allowed operations, ensuring we eventually reach a stable state where no further reductions are possible. However, each operation scan is O(n²), and potentially many iterations are needed, making it infeasible.

Key Insight

The crucial observation is that each element x can ultimately be replaced by any value y in the array such that y divides x. Once x is replaced by y, it can further be replaced by any divisor of y, but this does not expand the reachable set beyond all divisors present in the array.

Therefore, the optimal strategy is independent per element: for each x, we want the smallest value in the array that divides x. If no such value exists, x remains unchanged.

This reduces the problem to a divisor-checking problem using frequency lookup and enumeration of divisors up to sqrt(x).

Comparison Table

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * k) O(1) Repeatedly simulate replacements until convergence
Optimal O(n √m) O(m) Check divisors for each number using frequency set, m = max(nums[i])

Algorithm Walkthrough

The optimal algorithm works by precomputing which values exist in the array and then evaluating the best possible replacement for each element independently.

  1. First, construct a frequency array or hash set present that records which numbers appear in nums. This allows O(1) checks for whether a candidate divisor exists.
  2. Initialize a variable result_sum to accumulate the final minimized sum.
  3. For each number x in nums, attempt to find the smallest value d such that d is in the array and d divides x.
  4. To find such a divisor efficiently, iterate d from 1 to sqrt(x). If d divides x, check both d and x // d as candidate divisors.
  5. For each valid divisor candidate that exists in the array, track the minimum such value.
  6. If at least one valid divisor exists, add the minimum divisor to the result. Otherwise, add x itself.
  7. Return the accumulated sum.

Why it works

The correctness relies on the fact that the operation allows direct replacement from x to any divisor y already present in the array. Because divisibility is transitive, any multi-step replacement sequence collapses into a direct replacement by some divisor in the original set. Therefore, choosing the minimum reachable divisor for each element independently yields the globally optimal sum.

Python Solution

class Solution:
    def minArraySum(self, nums: list[int]) -> int:
        present = set(nums)
        max_val = max(nums)

        total = 0

        for x in nums:
            best = x

            d = 1
            while d * d <= x:
                if x % d == 0:
                    if d in present:
                        best = min(best, d)
                    other = x // d
                    if other in present:
                        best = min(best, other)
                d += 1

            total += best

        return total

Implementation Explanation

The solution first builds a set for constant-time membership checks. For each element x, it initializes best as x, meaning no replacement has been found yet.

It then iterates over all possible divisors up to sqrt(x). When a divisor d is found, both d and x // d are checked against the set of available values. If either exists, it is a valid replacement candidate.

The smallest valid candidate is chosen as the final value for x, and this value is accumulated into the total sum.

Go Solution

func minArraySum(nums []int) int64 {
    present := make(map[int]bool)
    for _, v := range nums {
        present[v] = true
    }

    var total int64 = 0

    for _, x := range nums {
        best := x

        for d := 1; d*d <= x; d++ {
            if x%d == 0 {
                if present[d] && d < best {
                    best = d
                }
                other := x / d
                if present[other] && other < best {
                    best = other
                }
            }
        }

        total += int64(best)
    }

    return total
}

Go-Specific Notes

The Go implementation uses a map[int]bool for membership checks instead of a set. This is idiomatic in Go since it lacks a built-in set type.

The result is stored in int64 to safely handle large sums, since the sum of up to 1e5 values each up to 1e5 may exceed 32-bit integer limits.

Worked Examples

Example 1: nums = [3, 6, 2]

We build present = {2, 3, 6}.

For 3, divisors are 1, 3. Only 3 is present, so best is 3.

For 6, divisors are 1, 2, 3, 6. Among these, 2, 3, and 6 exist, so best is 2.

For 2, divisors are 1, 2. Only 2 exists, so best is 2.

Final sum is 3 + 2 + 2 = 7.

Example 2: nums = [4, 2, 8, 3]

present = {2, 3, 4, 8}.

For 4, divisors are 1, 2, 4. Best is 2.

For 2, best is 2.

For 8, divisors are 1, 2, 4, 8. Best is 2.

For 3, only 3 exists.

Final array becomes [2, 2, 2, 3], sum is 9.

Example 3: nums = [7, 5, 9]

No number divides another within the set.

Each element remains unchanged, so sum is 21.

Complexity Analysis

Measure Complexity Explanation
Time O(n √m) Each element checks divisors up to sqrt(m), where m is max value
Space O(m) Storage for presence set or hash map

The algorithm is efficient because divisor enumeration is bounded by the square root of the maximum value, and membership checks are constant time.

Test Cases

# provided examples
assert Solution().minArraySum([3,6,2]) == 7  # basic reduction via divisors
assert Solution().minArraySum([4,2,8,3]) == 9  # multiple replacements to same base
assert Solution().minArraySum([7,5,9]) == 21  # no valid replacements

# edge cases
assert Solution().minArraySum([1,1,1]) == 3  # 1 replaces everything but already minimal
assert Solution().minArraySum([10]) == 10  # single element
assert Solution().minArraySum([2,3,5,7]) == 17  # primes only, no replacements
assert Solution().minArraySum([6,3]) == 6  # 6 can become 3
assert Solution().minArraySum([100000,1]) == 2  # 1 dominates all

Test Summary

Test Why
[3,6,2] validates standard divisor reduction
[4,2,8,3] checks multiple elements collapsing to same minimum
[7,5,9] ensures no-operation case works
[1,1,1] smallest possible value edge case
[10] single-element array
[2,3,5,7] prime numbers with no divisors
[6,3] direct divisibility replacement
[100000,1] global minimum dominates

Edge Cases

One important edge case is when the array contains only prime numbers. Since primes have no divisors other than 1 and themselves, and unless 1 is present, no replacement is possible. The implementation handles this correctly because no divisor in the set will be found during the scan, leaving values unchanged.

Another edge case is when the value 1 appears in the array. Since 1 divides every integer, every element can be reduced to 1. The divisor scan correctly identifies 1 as a valid replacement and ensures all elements become 1.

A third edge case is a single-element array. Since there are no other indices available, no operation is possible. The algorithm naturally handles this because it only considers divisors within the array; the element remains unchanged and is directly added to the sum.