Suppose you are given an integer array array [ ] and an integer S . k is another integer (may or may not be present in the array) such that if all elements in the array greater than k are replaced by k , the sum of all elements in the new array will be S . How will you design an linearithmic algorithm to find k ?
Example - Let the input array be [ 40 30 100 90 20 ] and S = 250 . Input array : [ 40 30 100 90 20 ] Sorted array : [ 20 30 40 90 100 ] Iteration \( 1 \) : \( CE_1 = 20 \) , \( Sum_1 = 20 + 4\times 20 = 100 < 250 \) Iteration \( 2 \) : \( CE_2 = 20+30 = 50 \), \( Sum_2 = 50 + 3\times 30 = 140 < 250 \) Iteration \( 3 \) : \( CE_3 = 50+40 = 90 \), \( Sum_3 = 90 + 2\times 40 = 170 < 250 \) Iteration \( 4 \) : \( CE_4 = 90+90 = 180 \), \( Sum_4 = 180 + 1\times 90 = 270 > 250 \) \( CE_3 + k \times 2 = S => 90 + k \times 2 = 250 \) \( \therefore\ k = (250-90) = 80 \) . Time complexity = \( O(nlogn) \). public static findK(int[] array, int S){ |