The Sieve (but not Eratosthenes')

Sieves are a technique in algorithms that lets you build a certain pattern from the ground up in NLogN. The most famous one is the Sieve of Eratosthenes, which lets you compute the prime (or actually the !primes) in NLogN. But you can use Sieves for other problems unrelated to primes. The one below is a good example. The NLogN comes simply from the inner loop condition which goes only to maxVal but it grows very fast, hence this condition here is the key to achieving the LogN (the N comes from the outer loop). Code is down below, cheers, ACC.

Minimize Array Sum Using Divisible Replacements - LeetCode

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

public class Solution {
    public long MinArraySum(int[] nums)
    {
        //NLogN
        Array.Sort(nums);
        int maxVal = nums.Max();

        //N
        Hashtable frequency = new Hashtable();
        foreach (int n in nums)
        {
            if(!frequency.ContainsKey(n)) frequency.Add(n, 0L);
            frequency[n] = (long)frequency[n] + 1;
        }

        //Sieve: NLogN
        long retVal = 0;
        foreach (int n in nums)
        {
            if (frequency.ContainsKey(n))
            {
                for (int i = 1; i * n <= maxVal; i++)
                {
                    if (frequency.ContainsKey(i * n))
                    {
                        retVal += (n * (long)frequency[i * n]);
                        frequency.Remove(i * n);
                    }
                }
            }
        }

        return retVal;
    }
}