Find k normalizing the elements greater than k in an array
  • timecomplexity
  • array
  • searching
  • linearithmictime
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (2341)

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 ?


Posted Answers


  • Sort the input array array [ ] in increasing order.
  • Take the first element of the sorted array. Add it with itself multiplied by the number of remaining elements in the array at the right side. Compare the sum with S .
  • If the sum is less than S , go to the next element and add it with the last element. This sum is our current cumulative element. Iterate through the array and repeat the last step recursively until the sum is greater than S .
  • If the sum is greater than S , compute the sum of the cumulative element at the previous iteration and k multiplied by the number of remaining elements in the array. This sum will be equal to S . Solve k arithmetically.

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){

/* Sort the input array */
array = Arrays.sort(array);

/* Variables */
int cumulativeElement = 0;
int sum = 0;

for(int i = 0; i < array.length; i++){

/* Find cumulative element at the current index */
cumulativeElement += array[i];
/* Find the sum at the current index */
sum += cumulativeElement + (array.length - i) * array[i];

/* When sum is less than S : continue the for loop */
if(sum < S)
Write PR;
/* When sum is greater than S : break the loop and calculate k */
if(sum >= S)
break;

}
/* Calculate k */
k = (S - *)/(array.length - i + 1);
Write PR : * = cumulativeElement at (i-1)th iteration
}

You need to Sign In to post your solution.