Skip to content

3927. Minimize Array Sum Using Divisible Replacements

Description

You are given an integer array nums.

You can perform the following operation any number of times:

  • Choose two indices a and b such that nums[a] % nums[b] == 0.
  • Replace nums[a] with nums[b].

Return the minimum possible sum of the array after performing any number of operations.

 

Example 1:

Input: nums = [3,6,2]

Output: 7

Explanation:

  • Choose a = 1, b = 2, where nums[a] = 6 and nums[b] = 2. Since 6 % 2 == 0, replace nums[1] with nums[2].
  • The array becomes [3, 2, 2].
  • No further operation reduces the sum. Thus, the final sum is 3 + 2 + 2 = 7.

Example 2:

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

Output: 9

Explanation:

  • Choose a = 0, b = 1, where nums[a] = 4 and nums[b] = 2. Since 4 % 2 == 0, replace nums[0] with nums[1].
  • Choose a = 2, b = 1, where nums[a] = 8 and nums[b] = 2. Since 8 % 2 == 0, replace nums[2] with nums[1].
  • The array becomes [2, 2, 2, 3].
  • No further operation reduces the sum. Thus, the final sum is 2 + 2 + 2 + 3 = 9.

Example 3:

Input: nums = [7,5,9]

Output: 21

Explanation:

  • There is no pair (a, b) such that nums[a] % nums[b] == 0.
  • Hence, no operation can be performed. The sum remains 7 + 5 + 9 = 21.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 10​​​​​​​5

Solutions

Solution 1

Thinking

\(n\le 10^5\), so we cannot simulate arbitrary replacements. An entry \(a\) may be overwritten by any \(b\) that divides it, and repeating that yields the smallest array value that divides \(a\).

Globally, each number should become the smallest array element that divides it. If \(m\) is the global minimum, every multiple of \(m\) can become \(m\) and the rest stay themselves; the answer is the sum of those finals.

This directory has no implemented solution yet; the walkthrough stops at that per-position minimum divisor from the array.

1


1


1


1

Comments