The sort is what makes this O(n*log n). The processing after the sort is O(N).
So to describe the algorithm, after sorting A, it steps through the sorted array, determining what the value of K would have to be at that point such that setting the remaining values to K would cause the sum to be S. S-sum is the required total of the rest of the array, and that total is divided among the len(A) - index remaining values. If solution is less than the previous value in A, then it is not a valid solution because that previous value would have been set to K as well. If solution is greater than the current value, the the current value would not be replaced. Thus, it is necessary that prev < solution <= value. There are some unstated assumptions. For example, if the values in A can be negative, there could be problems. And if values in A must be integers, the value of solution might not give a result exactly equal to S. But if A contains positive real numbers I think that it will work. Don On Sunday, March 30, 2014 10:02:08 AM UTC-4, atul007 wrote: > > 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.
