Minimize Array Sum Using Divisible Replacements | Leetcode 3927

//Solution-1: Space optimized solution
//TC: O(NlogN + M (logN)^2)
//SC: O(N)
class Solution {
    #define ll long long
public:
    long long minArraySum(vector<int>& nums) {
        int n = nums.size();
        //Step-1: Build ordered_map using the nums array
        map<ll,ll> freq;
        int max_ele = INT_MIN;
        for(int &ele: nums){
            freq[ele]++;
            max_ele = max(max_ele,ele);
        }

        //Step-2: Find total sum by marking the dividends
        ll sum=0;
        for(auto &[ele,count]: freq){
            if(count==0)    //Skip freq=0 elements
                continue;
            for(ll curr = ele; curr<=max_ele; curr+=ele){
                if(freq.count(curr) and freq[curr]>0){
                    sum += freq[curr] * ele;
                    freq[curr] = 0;
                }
            }
        }
        return sum;
    }
};


//Solution-2: Time optimized solution
//TC: O(N + MlogN))
//SC: O(M)
class Solution {
    #define ll long long
public:
    long long minArraySum(vector<int>& nums) {
        // Step-1: Find max_ele and mark the freq
        ll max_ele = *max_element(nums.begin(),nums.end());
        vector<ll> freq(max_ele+1,0);
        for(int &ele: nums)
            freq[ele]++;
        
        // Step-2: Mark the dividends
        ll sum = 0;
        for(ll divisor=1;divisor<=max_ele;++divisor){
            if(freq[divisor]==0)
                continue;
            
            //Else, try for all the multiples and see if there are any such dividend
            for(ll curr=divisor;curr<=max_ele;curr+=divisor){
                if(freq[curr]>0){
                    sum += freq[curr] * divisor;
                    freq[curr] = 0;
                }
            }
        }
        return sum;
    }
};
/*
//Java
//Solution-1: Space optimized solution
//TC: O(NlogN + M (logN)^2)
//SC: O(N)
class Solution {
    public long minArraySum(int[] nums) {
        int n = nums.length;

        Map<Long, Long> freq = new TreeMap<>();
        long maxEle = Long.MIN_VALUE;

        for (int ele : nums) {
            freq.put((long) ele, freq.getOrDefault((long) ele, 0L) + 1L);
            maxEle = Math.max(maxEle, ele);
        }

        long sum = 0;

        for (Map.Entry<Long, Long> entry : freq.entrySet()) {
            long ele = entry.getKey();
            long count = entry.getValue();

            if (count == 0) continue;

            for (long curr = ele; curr <= maxEle; curr += ele) {
                if (freq.containsKey(curr) && freq.get(curr) > 0) {
                    sum += freq.get(curr) * ele;
                    freq.put(curr, 0L);
                }
            }
        }

        return sum;
    }
}

//Python
//Solution-1: Space optimized solution
//TC: O(NlogN + M (logN)^2)
//SC: O(N)
class Solution:
    def minArraySum(self, nums):
        freq = {}
        max_ele = max(nums)

        for ele in nums:
            freq[ele] = freq.get(ele, 0) + 1

        sum_val = 0

        for ele in sorted(freq.keys()):
            count = freq[ele]
            if count == 0:
                continue

            curr = ele
            while curr <= max_ele:
                if curr in freq and freq[curr] > 0:
                    sum_val += freq[curr] * ele
                    freq[curr] = 0
                curr += ele

        return sum_val


//JAVA
//Solution-2: Time optimized solution
//TC: O(N + MlogN))
//SC: O(M)
class Solution {
    public long minArraySum(int[] nums) {
        long maxEle = Arrays.stream(nums).max().getAsInt();

        long[] freq = new long[(int) maxEle + 1];
        for (int ele : nums) {
            freq[ele]++;
        }

        long sum = 0;

        for (long divisor = 1; divisor <= maxEle; divisor++) {
            if (freq[(int) divisor] == 0) continue;

            for (long curr = divisor; curr <= maxEle; curr += divisor) {
                if (freq[(int) curr] > 0) {
                    sum += freq[(int) curr] * divisor;
                    freq[(int) curr] = 0;
                }
            }
        }

        return sum;
    }
}

//Python
//Solution-2: Time optimized solution
//TC: O(N + MlogN))
//SC: O(M)
class Solution:
    def minArraySum(self, nums):
        max_ele = max(nums)
        freq = [0] * (max_ele + 1)

        for ele in nums:
            freq[ele] += 1

        sum_val = 0

        for divisor in range(1, max_ele + 1):
            if freq[divisor] == 0:
                continue

            curr = divisor
            while curr <= max_ele:
                if freq[curr] > 0:
                    sum_val += freq[curr] * divisor
                    freq[curr] = 0
                curr += divisor

        return sum_val
*/