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 an...