Posts

Learnt a lot about the two problems. Not very basic intuition to see, would need a lot of practise to see. Question 2: Really good question. I learnt how to find powers of two of a number by checking if the kth bit of the binary represenation of that number is set. Noted down the learning in algorithms notes. https://leetcode.com/contest/biweekly-contest-89/problems/range-product-queries-of-powers/ Question 3: This is a different type of problem. This is not a normal intuition. Just averaging out the values over the entire array makes it quite simple. (not a solution that can be thought of in a live problem solving environment, requires a lot of practise to see) Let's assume nums includes two numbers only: [num1, num2]. According to the problem description, there is no way to decrease num1. So manipulations are possible only with num2. 3 possible cases can be considered: 1. num1 > num2: nothing can be done to decrease max(nums), num1 shall be returned; 2. num1 = num2: same as above; 3. num1 < num2: we can decrease num2 increasing num1 so both are equal (or almost equal). If (num1 + num2) % 2 == 0 the resulting maximum value is (num1 + num2) // 2, otherwise 1 should be added to the average. Now let's assume nums = [num1, num2, num3] and we already equalized num1, num2. We can only decrease num3 thus increasing num1 and num2, but this action does not make any sense if num3 is less or equal to max(nums1, nums2). If num3 is the maximum we can equalize these 3 numbers making them as close to sum(num1, num2, num3)/3 as possible. So the algorithm is to iterate over nums elements calculating the average and updating the maximum value if current average > current max. https://leetcode.com/contest/biweekly-contest-89/problems/minimize-maximum-of-array/