Problem statement

https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/

Solution

We can use binary search here: let check(v) be sum of all array, if we perform operation with value v.

Complexity

It is O(n log M) for time and O(n) for space.

Code

class Solution:
    def findBestValue(self, arr, t):
        def check(v):
            return sum(min(a, v) for a in arr)

        beg, end = 0, max(arr)
        while beg + 1 < end:
            mid = (beg + end) // 2
            if check(mid) <= t:
                beg = mid
            else:
                end = mid
                
        return beg + (2*t > check(beg) + check(beg + 1))

Remark

There is also O(n log n) time complexity solution, if we sort array and then check what happens if we take the biggest k values.