Minimize Array Sum Using Divisible Replacements
You are given an integer array nums.
You can perform the following operation any number of times:
- Choose two indices
aandbsuch thatnums[a] % nums[b] == 0. - Replace
nums[a]withnums[b].
Return the minimum possible sum of the array after performing any number of operations.
Example 1
Input
nums = [3,6,2]Output
7Replacing
6 with 2 gives [3, 2, 2], and no further operation reduces the sum, so the minimum sum is 7.Example 2
Input
nums = [4,2,8,3]Output
9Replacing
4 and 8 with 2 gives [2, 2, 2, 3], and no further operation reduces the sum, so the minimum sum is 9.Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5