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