Posts

Miller-Rabin Primality Test and Caching II

-
Image
A bit overkill to use MRP here. Also, there is probably a way to do it a little faster by scanning from left, then right, and stopping at the first prime number from each side. Code is down below, cheers, ACC. 3115. Maximum Prime Difference Medium 76 6 Add to List Share You are given an integer array  nums . Return an integer that is the  maximum  distance between the  indices  of two (not necessarily different) prime numbers in  nums .   Example 1: Input:   nums = [4,2,9,5,3] Output:   3 Explanation:   nums[1] ,  nums[3] , and  nums[4]  are prime. So the answer is  |4 - 1| = 3 . Example 2: Input:   nums = [4,8,2,8] Output:   0 Explanation:   nums[2]  is prime. Because there is just one prime number, the answer is  |2 - 2| = 0 .   Constraints: 1 <= nums.length <= 3 * 10 5 1 <= nums[i] <= 100 The input is generated such that the number of prime numbers in the  nums  is at least one. public class Solution { public static Hashtable primes100 = null; public int MaximumP
Post a Comment
Read more

Standard Priority Queue V: PQueue as a Sorting Mechanism

-
Image
Priority Queues can be used as a standard NLogN sorting mechanism. Usually it isn't used as sorting due to the extra space required for the heap, but in terms of execution time it is as efficient as MergeSort for the worst case and even better than QuickSort on some cases. If you have a handy implementation of PQueue, don't be afraid of using it for sorting. Problem below requires a sorting of the elements based on the X-coordinate, followed by a linear scanning counting the number of rectangles. PQueue comes to the rescue here. Code is down below, cheers, ACC. Minimum Rectangles to Cover Points - LeetCode 3111. Minimum Rectangles to Cover Points Medium 47 2 Add to List Share You are given a 2D integer array  points , where  points[i] = [x i , y i ] . You are also given an integer  w . Your task is to  cover   all  the given points with rectangles. Each rectangle has its lower end at some point  (x 1 , 0)  and its upper end at some point  (x 2 , y 2 ) , where  x 1  <= x 2 , 
Post a Comment
Read more