Tricky Interview question on searching

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.

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