3927. 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
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
long long minArraySum(vector<int>& nums) {
unordered_map<long long, long long> freq;
long long res = 0;
for(auto& n : nums) freq[n]++;
for(auto& [k,v] : freq) {
long long pick = k;
for(int i = 1; i * i <= k and pick > i; i++) {
if(k % i) continue;
long long a = i, b = k / i;
if(freq.count(a)) pick = min(pick,a);
if(freq.count(b)) pick = min(pick,b);
}
res += pick * v;
}
return res;
}
};
|
