Tricky Interview question on searching

Question

I recently heard this question from a friend who was asked this in an interview. He was not able to figure it out and i have not yet found any efficient solution to it either. I hope there is an algorithmist here who can show me a new approach

Question:

Given an array A and a number S', provide an efficient algorithm (nlogn) to find a number K such that if all elements in A greater than K are changed to K, the sum of all elements in the resulting array will be S'.

Example, given A: [90,30,100,40,20] and S' = 210, K will be 60.

Answer 1

Written in Python, which should be quite readable even if you don't know the language:

#!/usr/bin/env python

A = [90, 30, 100, 40, 20]
S = 210
K = 60

A    = sorted(A)
prev = 0
sum  = 0

for index, value in enumerate(A):
    # What do we need to set all subsequent values to to get the desired sum?
    solution = (S - sum) / (len(A) - index)

    # That answer can't be too big or too small.
    if prev < solution <= value:
        print solution

    sum += value
    prev = value

Result:

60

Sorting is O(n log n) and the loop is O(n). Combined the algorithm as a whole is therefore O(n log n).

Answer 2

First sort the list smallest to largest and find how long it is. Then start adding up the numbers one by one. At each step, also find a lower limit on what the sum could be - what the sum of the whole list would be, if all of the rest of the numbers you haven't added in yet are the same as the current number.

At some point this lower limit on the sum will go from being smaller than S', to larger than S', and at that point you can do some arithmetic to determine what the cutoff should be. eg (C = current sum, L = lower limit on total sum):

start
[90 30 100 40 20]
sort
[20 30 40 90 100]
start adding up the sum
C1 = 20
L1 = 20 + 4*20 = 100 &lt 210

C2 = 20 + 30 = 50
L2 = 50 + 3*30 = 140 &lt 210

C3 = 50 + 40 = 90
L3 = 90 + 2*40 = 170 &lt 210

C4 = 90 + 90 = 180
L4 = 180 + 1*90 = 270 &gt 210 //too big!

S' = C3 + K*2
therefore
K = (S'-C3)/2 = 60

Answer 3

This can be accomplished without sorting in O(n) time by using a variation on linear time select as follows (note that the running times of the iterations of the while loop form a geometric series -- the partition subroutine splits a range of an array, from lower to upper, into elements less than or greater than the element of rank mid, and the running time is proportional to the size of the range of the array):

foo(x, s) {
  sumBelow = 0;
  lower = 0;
  upper = x.size();
  while (lower + 1 != upper) {
    mid = (upper + lower) / 2;
    partition(x, lower, mid, upper); // O(upper - lower) time
    sumb = 0;
    maxb = 0; // assuming non-negative to avoid use of flags
    for (i = lower; i < mid; i++) {
      sumb += x[i];
      maxb = max(maxb, x[i]);
    }
    if (sumBelow + sumb + maxb * (x.size() - mid) <= s) {
      lower = mid;
      sumBelow += sumb;
    } else {
      upper = mid;
    }
  }
  K = (s - sumBelow) / (x.size() - lower);
  if (K > maxElement(x)) return error();
  else return K;
}