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 [email protected].
