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

Interview question: three arrays and O(N*N)

Assume we have three arrays of length N which contain arbitrary numbers of type long. Then we are given a number M (of the same type) and our mission is to pick three numbers A, B and C one from each array (in other words A should be picked from first array, B from second one and C from third) so the sum A + B + C = M.

Question: could we pick all three numbers and end up with time complexity of O(N²)?

---

Illustration:

Arrays are:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

And M we've been given is 19. Then our choice would be 8 from first, 4 from second and 7 from third.

This can be done in O(1) space and O(N²) time.

First lets solve a simpler problem:
Given two arrays A and B pick one element from each so that their sum is equal to given number K.

Sort both the arrays which takes O(NlogN).
Take pointers i and j so that i points to the start of the array A and j points to the end of B.
Find the sum A[i] + B[j] and compare it with K

• if A[i] + B[j] == K we have found the pair A[i] and B[j]
• if A[i] + B[j] < K, we need to increase the sum, so increment i.
• if A[i] + B[j] > K, we need to decrease the sum, so decrement j.

This process of finding the pair after sorting takes O(N).

Now lets take the original problem. We've got a third array now call it C.

So the algorithm now is :

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

The outer loop runs N times and for each run we do a O(N) operation making the entire algorithm O(N²).