Hello,
i found this question online and its solution too....But i am not able to
fully understand the solution.Need your help to proof correctness of the
algo.
Question is as follows :-
*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.*
*Ans)*
#!/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
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
