Prime Subtraction Operation - Sieve of Eratosthenes & Binary Search [JS]
Description Solution: Sieve of Eratosthenes & Binary Search Use the Sieve of Eratosthenes to find all the prime numbers up to the maximum number. Greedily subtract the biggest possible prime number <= nums[i] where nums[i] - prime > nums[i - 1] Use binary search to find this prime. Time Complexity: O(n log(n)) 96ms Space Complexity: O(n) 48.8MB var primeSubOperation = function ( nums ) { let primes = getPrimes ( Math . max ( ... nums ) ) ; for ( let i = 0 ; i < nums . length ; i ++ ) { let low = 0 , high = primes . length - 1 ; while ( low < high ) { let mid = Math . ceil ( ( low + high ) / 2 ) ; let isValid = i === 0 ? primes [ mid ] < nums [ i ] : primes [ mid ] < nums [ i ] && nums [ i ] - primes [ mid ] > nums [ i - 1 ] ; if ( isValid ) { low = mid ; } else { high = mid - 1 ; } ...