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 algogeeks+unsubscr...@googlegroups.com.
