Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.
In case of a tie, return the minimum such integer.
Notice that the answer is not neccesarilly a number from arr.
 
Example 1:
Input: arr = [4,9,3], target = 10
Output: 3
Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2:
Input: arr = [2,3,5], target = 10
Output: 5

Example 3:
Input: arr = [60864,25176,27249,21296,20204], target = 56803
Output: 11361

 
Constraints:

1 <= arr.length <= 10^4
1 <= arr[i], target <= 10^5

Difficulty: interview

Starter code:

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        

Solutions:
class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        n = len(arr)
        for i in range(n):
            sol = round(target / n)
            if arr[i] >= sol:
                return sol
            target -= arr[i]
            n -= 1
        return arr[-1]

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        s, n = 0, len(arr)
        
        for i in range(n):
            ans = round((target - s)/n)
            if ans <= arr[i]: return ans 
            s += arr[i]
            n -= 1
            
        return arr[-1]

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr=sorted(arr)
        sum1=0
        mindiff=float('inf')
        val=0
        n=len(arr)
        for num in arr:
            val=(target-sum1)/n
            if val<=num:
                val=int(val)
                if val+1<=num:
                    if abs(target-sum1-n*val)<=abs(target-sum1-n*(val+1)):
                        return val
                    else:
                        return val+1
                else:
                    return val
            else:
                n-=1
                sum1+=num
                
        return arr[-1]
                
                


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        min_diff = float('inf')
        n = len(arr)
        best = None
        counter = Counter(arr)
        count = 0
        partial_sum = sum(arr)
        sorting = sorted(counter, key=lambda x: -x)
        
        rounding = round(target / n)
        diff2 = abs(rounding * n - target)
        if rounding <= sorting[-1] and diff2 < min_diff:
            best = rounding
            min_diff = abs(rounding * n - target)

        for i in range(len(sorting)):
            num = sorting[i]
            count += counter[num]
            partial_sum -= num * counter[num]
            diff = abs(count * num + partial_sum - target)
            
            if diff <= min_diff:
                min_diff = diff
                best = num
                
            rounding = round((target - partial_sum) / count)
            if rounding > 0 and i < len(sorting) - 1 and rounding > sorting[i + 1] and rounding < sorting[0]:
                diff2 = abs(rounding * count + partial_sum - target)
                if diff2 < min_diff:
                    best = rounding
                    min_diff = diff2
            
        return best


def binsearch(arr,x):
    if(x<arr[0]):
        return 0
    n=len(arr)
    if(arr[n-1]<=x):
        return n
    s=0
    e=len(arr)-1
    ret=n
    while(s<=e):
        mid=(s+e)//2
        if(arr[mid]<=x):
            s=mid+1
        else:
            ret=mid
            e=mid-1
    return ret
class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        n=len(arr)
        arr.sort()
        prefix=[]
        prefix.append(arr[0])
        for i in range(1,n):
            prefix.append(prefix[i-1]+arr[i])
        prefix.append(0)
        low=0
        hi=arr[n-1]
        minret=1
        mindiff=sys.maxsize
        while(low<=hi):
            mid=(low+hi)//2
            x=binsearch(arr,mid)
            val=prefix[x-1]+(n-x)*mid
            diff=abs(val-target)
            if(diff==mindiff and mid<minret):
                minret=mid
            elif(diff<mindiff):
                mindiff=diff
                minret=mid 
            if(val<target):
                low=mid+1
            else:
                hi=mid-1
        return minret
            


# class Solution(object):
#     def getRes(self,arr,t):
#         nums = [t if num >= t else num for num in arr]
#         return sum(nums)
    
#     def findBestValue(self, arr, target):
#         \"\"\"
#         :type arr: List[int]
#         :type target: int
#         :rtype: int
#         \"\"\"
#         l = 1
#         h = max(arr)
        
#         while l <= h:
#             mid = (h-l)//2 + l
#             curr = self.getRes(arr,mid)
#             if curr == target:
#                 return mid
#             elif curr < target:
#                 l = mid+1
#             else:
#                 h = mid-1
#         if abs(self.getRes(arr,l) - target) < abs(self.getRes(arr,h) - target):
#             return l
#         return h

class Solution:
    def score(self, value):
        res = 0
        for e in self.arr:
            if e > value:
                res += value
            else:
                res += e
        return res
    
    def findBestValue(self, arr: List[int], target: int) -> int:
        self.arr = arr[:]
        l, h = 1, max(arr)
        while l < h:
            m = (l+h) // 2
            if self.score(m) < target:
                l = m + 1
            else:
                h = m
        #print(l, h)        
        s1 = abs(self.score(h-1)-target)
        s2 = abs(self.score(h)-target)
        if s1 <= s2:
            return h-1
        return h


# class Solution:
#     def findBestValue(self, arr: List[int], target: int) -> int:
#         #int arr 
#         #target is what I want
#         #Return value

#         #WANT -> Return the value s.t 
# #Constraint -> CHANGE all integers > value in the array to be EQUAL to value. 
# #Get the sum of the array as CLOSE (abs diff) as possible to the target


# #In case of tie return the min int 

#         def mutated_sum(left, right, target, value):
#             # abs_diff = 0
#             cur_sum = 0
#             for num in arr:
#                 if num >= value: 
#                     cur_sum += value 
#                 elif num < value: 
#                     cur_sum += num 
                    
                    
#              #abs_diff is 1
#             return cur_sum
#         #[4, 9, 3] target = 10 
#         left = 1
#         right = max(arr)
#         min_diff = target 
#         prev_min_val = right
        
#         #left = 3 
#         #right = 4
#         while left < right: 
#             value = left + (right - left) // 2
#             cur_sum = mutated_sum(left, right, target, value)
#             if cur_sum == target:
#                 return value
#             curr_diff = abs(target - cur_sum)
            
#             if curr_diff < min_diff:
#                 min_diff = curr_diff
#                 prev_min_val = value
#             elif curr_diff == min_diff:
#                 prev_min_val = min(prev_min_val, value)
#             if cur_sum <= target: #IF MY CUR_SUM is < target 
#                 #THE MORE I MOVE LEFT the farther I am far from target
#                 # min_diff = cur_diff #min_diff is 1 
#                 left = value
            
#             else: #cur_sum >= target
#                 right = value - 1
            
#         if abs(mutated_sum(left,right, target,left) - target) < \\
#         abs(mutated_sum(left,right, target,right)) - target:
#             return left
                
#         return right
            
            
            
            
            
            


# class Solution(object):
#     def getRes(self,arr,t):
#         nums = [t if num >= t else num for num in arr]
#         return sum(nums)
    
#     def findBestValue(self, arr, target):
#         \"\"\"
#         :type arr: List[int]
#         :type target: int
#         :rtype: int
#         \"\"\"
#         l = 1
#         h = max(arr)
        
#         while l <= h:
#             mid = (h-l)//2 + l
#             curr = self.getRes(arr,mid)
#             if curr == target:
#                 return mid
#             elif curr < target:
#                 l = mid+1
#             else:
#                 h = mid-1
#         if abs(self.getRes(arr,l) - target) < abs(self.getRes(arr,h) - target):
#             return l
#         return h

# class Solution:
#     def score(self, value):
#         res = 0
#        # print(self.arr)
#         for e in self.arr:
#             if e > value:
#                 res += value
#             else:
#                 res += e
#         return res
    
#     def findBestValue(self, arr: List[int], target: int) -> int:
#         self.arr = arr[:]
#         l, h = 1, max(arr)
#         while l < h:
#             m = (l+h) // 2
#             if self.score(m) < target:
#                 l = m + 1
#             else:
#                 h = m
#         #print(l, h)        
#         s1 = abs(self.score(h-1)-target)
#         print('s1', s1)
#         print(h)
#         # print(l)
       
#         s2 = abs(self.score(h)-target)
#         print('s2', s2)
#         if s1 <= s2:
#             return h-1
#         return h


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        #int arr 
        #target is what I want
        #Return value

        #WANT -> Return the value s.t 
#Constraint -> CHANGE all integers > value in the array to be EQUAL to value. 
#Get the sum of the array as CLOSE (abs diff) as possible to the target


# #In case of tie return the min int 

        def mutated_sum(value):
            # print(arr)
            # abs_diff = 0
            cur_sum = 0
            for num in arr:
                if num > value: 
                    cur_sum += value 
                else: 
                    cur_sum += num 
                    
                    
             #abs_diff is 1
            return cur_sum
        #[4, 9, 3] target = 10 
        left = 1
        right = max(arr)
        
        #left = 3 
        #right = 4
        while left < right: 
            value = left + (right - left) // 2
            cur_sum = mutated_sum(value)
    
            if cur_sum < target: #IF MY CUR_SUM is < target 
                #THE MORE I MOVE LEFT the farther I am from target
                # min_diff = cur_diff #min_diff is 1 
                left = value + 1
            
            else: #cur_sum >= target
                right = value
            
      
        s1 = abs(mutated_sum(left - 1) - target)
        print(s1)
        # print(left_abs)
        # print(right)
        # print(left)
        s2 = abs(mutated_sum(left) - target)
        # print(right_abs)
        print(s2)
        if s1 <= s2:
            return left - 1
        return left 
            
            
            
            
            
            


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        # binary search
        lo, hi = 0, min(max(arr), 10**5)
        while lo <= hi:
            m = (lo+hi)//2
            s = sum(m if x > m else x for x in arr)
            if s > target:
                lo, hi = lo, m-1
            else:
                lo, hi = m+1, hi
                
        sl = sum(lo if x > lo else x for x in arr)
        sh = sum(hi if x > hi else x for x in arr)
        
        if abs(target - sl) >= abs(target - sh):
            return hi # hi is lower than lo
        else:
            return lo

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        
        total = sum(arr)
        if total <= target:
            return max(arr)
        
        arr = sorted(arr)

        min_num = target // len(arr)
        if min_num <= arr[0]:
            below = len(arr) * min_num
            above = len(arr) * (min_num + 1)

            if abs(target - below) <= abs(target - above):
                return min_num
            else:
                return min_num + 1
        return self.findBestValue(arr[1:], target - arr[0])

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        heapq._heapify_max(arr)
        steps = []
        last = heapq._heappop_max(arr)
        s = last
        c = 1
        
        while len(arr) > 0:
            v = heapq._heappop_max(arr)
            s += v
            
            if v != last:
                steps.append([c, last])
                last = v
            
            c += 1
        
        steps.append([c, last])
        
        i = 0
        bestDiff = s - target
        bestValue = steps[0][1]
        
        while i < len(steps):
            t = int((s - target) / steps[i][0])
            diff = steps[i][0] * t
            
            if i != len(steps)-1:
                diff = steps[i][0] * (steps[i][1] - steps[i+1][1])    
            
            if s - diff > target and i != len(steps)-1:
                s -= diff
                bestDiff = s - target
                bestValue = steps[i+1][1]

                i += 1
            elif s - diff == target:
                if i != len(steps)-1:
                    return steps[i+1][1]
                else:
                    return steps[i][1] - t
            else:
                diff1 = s - (steps[i][0] * t)
                diff2 = s - (steps[i][0] * (t+1))
                
                if bestDiff < abs(diff1 - target):
                    return bestValue
                
                if abs(diff1 - target) >= abs(diff2 - target):
                    return steps[i][1] - (t+1)
                else:
                    return steps[i][1] - t
                
        return bestValue
                


import bisect
class Solution:
        
    def findBestValue(self, arr: List[int], target: int) -> int:
        i, j = 0, max(arr)
        while i <= j: 
            mid = (i + j) // 2
            dist = sum(v if v < mid else mid for v in arr)
            # print(i, j, mid, dist)
            if dist == target: 
                return mid
            elif dist < target:
                i = mid + 1 
            else:
                j = mid - 1 
        
        disti = sum(v if v < i else i for v in arr)
        disti_1 = sum(v if v < (i-1) else (i-1) for v in arr)
        print((disti, disti_1, i, j))
          
        return i if abs(disti-target)  < abs(disti_1 - target) else (i-1) 
                
        
        
            
        


import math

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        
        n = len(arr)
        arr.sort()
        
        def get_candidates(sm, k, l, r):
            # sm + k * x ≈ target
            if k == 0:
                yield abs(sm - target), l
            else:
                y = math.floor((target - sm) / k)
                for x in [y, y + 1]:
                    x = max(l, min(r, x))
                    yield abs(sm + k * x - target), x
                
        def get_segments():
            sm = 0
            for i in range(n):

                l = 0 if i == 0 else arr[i - 1]
                r = arr[i] - 1

                if l <= r:
                    yield sm, n - i, l, r

                sm += arr[i]

            yield sm, 0, arr[-1], int(1e9)

        return min((xd for t in get_segments() for xd in get_candidates(*t)))[1]



class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        preSum = [0]
        for num in arr:
            preSum.append(preSum[-1]+num)
        arrLen = len(arr)
        
        def checkSum(x):
            l = 0
            r = arrLen - 1
            if x <= arr[0]:
                return x*arrLen
            if x >= arr[r]:
                return preSum[r+1]
            while r > l:
                m = (r + l)//2
                if arr[m] < x:
                    l = m + 1
                else:
                    r = m
            return preSum[l] + (arrLen-l)*x
        
        ll = 0
        rr = arr[-1]
        if preSum[arrLen] <= target:
            return arr[arrLen - 1]
        while rr > ll:
            mm = (rr + ll) // 2
            if checkSum(mm) < target:
                ll = mm + 1
            else:
                rr = mm
        if abs(checkSum(ll) - target) >= abs(checkSum(ll-1) - target):
            return ll - 1
        else:
            return ll
        


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        s = sum(arr)
        m = max(arr)
        if s <= target:
            return m
        l, r = 1, m+1
        while l < r:
            mid = (l+r) // 2
            cur = self.getSum(arr, mid)
            if cur == target:
                return mid
            elif cur < target:
                l = mid+1
            else:
                r = mid
        s1 = self.getSum(arr, l)
        s2 = self.getSum(arr, l-1)
        return l if abs(s1-target) < abs(s2-target) else l-1
    
    def getSum(self, arr, mid):
        s = 0
        for i in range(len(arr)):
            s += mid if arr[i] > mid else arr[i]
        return s


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        low = 0 
        high = (1 << 32)
        closest_diff = None
        closest_index = None
        while ((high - low) > 1):
            mid = (high + low) // 2
            mid_val = self.helper(arr,mid)
            if (closest_diff == None) or (closest_diff > abs(target - mid_val)):
                closest_index = mid
                closest_diff = abs(target - mid_val)
            elif (closest_diff == abs(target - mid_val) and mid < closest_index):
                closest_index = mid
                closest_diff = abs(target - mid_val)
            if (mid_val < target) and (mid <= arr[len(arr) - 1]):
                low = mid
            else:
                high = mid
                
        high_val = self.helper(arr,high)
        if (closest_diff == None) or (closest_diff > abs(target - high_val)):
            closest_index = high
            closest_diff = abs(target - high_val)
        low_val = self.helper(arr,low)
        if (closest_diff == None) or (closest_diff > abs(target - low_val)):
            closest_index = low
            closest_diff = abs(target - low_val)
        elif (closest_diff == low_val and low < closest_index):
            closest_index = low
            closest_diff = abs(target - low_val)
        return closest_index
    
    def helper(self,arr,val):
        curr_sum = 0
        for num in arr:
            if num < val:
                curr_sum += num
            else:
                curr_sum += val
        return curr_sum

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        n = len(arr)
        if sum(arr) <= target:
            return max(arr)
        
        left, right = 0, max(arr)
        
        while(left <= right):
            
            #print(left, right)
            if left == right:
                return left
            
            if left == right -1:
                sleft, sright = 0, 0
                
                for a in arr:
                    if a < left:
                        sleft += a
                    else:
                        sleft += left
                    
                    if a < right:
                        sright += a
                    else:
                        sright += right
                
                if abs(sleft - target) <= abs(sright - target):
                    return left
                else:
                    return right
                
            mid = (left + right) // 2
            midarr = []
            
            for a in arr:
                if a < mid:
                    midarr.append(a)
                else:
                    midarr.append(mid)
            
            midsum = sum(midarr)
            if midsum < target:
                    
                left = mid
            else:
                right = mid
        


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:

        arr = sorted(arr, reverse=True)
        print(arr)
        for i in range(len(arr) - 1, -1, -1):

            sol = round(target / (i + 1))

            if arr[i] >= sol:
                return sol
            target -= arr[i]
            
        return arr[0]
                



class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        low = 0
        high = max(arr)
        while low < high:
            mid = low + (high-low)//2
            if self.sol(mid,arr,target) <= self.sol(mid+1,arr,target):
                high = mid
            else:
                low = mid+1
        return low
    
    def sol(self,n,num,target):
        result = 0
        for i in num:
            if i > n:
                result += n
            else:
                result += i
        return abs(result-target)

class Solution:
    def check(self, arr, val):
        total = 0
        for i, value in enumerate(arr):
            if value >= val:
                return total + (len(arr) - i) * val 
            total += value
        return total
        
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        hi = max(arr)
        lo = 0
        mid = (lo+hi) // 2
        
        limit = hi
        low_value = abs(self.check(arr, hi) - target)
        
        while lo <= hi:
            calculated_value = self.check(arr, mid)
            if calculated_value >= target:
                hi = mid - 1
                
            if calculated_value <= target:
                lo = mid + 1
                
            diff = abs(calculated_value - target)
            if diff < low_value or (diff == low_value and mid < limit):
                limit = mid
                low_value = diff
                
            mid = (hi + lo) // 2
            
        return limit
            
    def findBestValue_fast(self, arr, target):
        arr.sort()
        ilen = len(arr)

        for i in arr:
            ideal = round(target / ilen) 
            if ideal <= i:
                return ideal
            target -= i
            ilen -= 1


        return arr[-1]
                


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        minVal = 0
        maxVal = arr[0] 
        for val in arr:
            if val < minVal:
                minVal = val
            if val > maxVal:
                maxVal = val
        low = minVal 
        high = maxVal 


        while(low < high):
            mid = high - (high-low)//2

            if(self.mutationSum(mid, arr) <= target):
                low = mid
            else:
                high = mid-1
        
        if (self.mutationSum(low, arr) == target):
            return low
        
        closestBelowInput = low
        closestBelowVal = self.mutationSum(closestBelowInput, arr)
        
        low = minVal 
        high = maxVal 
        while(low < high):
            mid = low + (high-low)//2

            if(self.mutationSum(mid, arr) >= target):
                high = mid
            else:
                low = mid + 1
        if(self.mutationSum(high, arr) == target):
            return high

        closestAboveInput = high 
        closestAboveVal = self.mutationSum(closestAboveInput, arr)

        if (target - closestBelowVal) <= (closestAboveVal - target):
            return closestBelowInput
        
        return closestAboveInput

    def mutationSum(self, m, arr):
        total = 0
        for val in arr:
            if(val > m):
                total += m
            else:
                total += val
        return total

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        l, r, minDiff, res = 0, max(arr) + 1, float('inf'), float('inf')
        while l < r:
            m = l + (r - l) // 2
            # m is too big, since few num are reduced to m.
            currSum = 0
            for n in arr:
                currSum += min(m, n)
            if currSum == target:
                return m
            currDiff = abs(target - currSum)
            if currDiff < minDiff:
                minDiff = currDiff
                res = m
            elif currDiff == minDiff:
                res = min(res, m)
            if currSum > target:
                r = m
            else:
                l = m + 1
        return res
            
    # https://www.youtube.com/watch?v=j0KejYpI_Mc
    def findBestValue1(self, arr: List[int], target: int) -> int:
        arr.sort()
        length = len(arr)
        for n in arr:
            # round is different to //. round(1.2) = 1, round(1.6) = 2
            res = round(target / length)
            if n >= res:
                return res
            target -= n
            length -= 1
        # return biggest num
        return arr[-1]

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        # r need be max(arr) + 1, not target
        l, r, minDiff, res = 0, max(arr) + 1, float('inf'), float('inf')
        while l < r:
            m = l + (r - l) // 2
            # m is too big, since few num are reduced to m.
            currSum = 0
            for n in arr:
                currSum += min(m, n)
            if currSum == target:
                return m
            currDiff = abs(target - currSum)
            if currDiff < minDiff:
                minDiff = currDiff
                res = m
            elif currDiff == minDiff:
                res = min(res, m)
            if currSum > target:
                r = m
            else:
                l = m + 1
        return res
            
    # https://www.youtube.com/watch?v=j0KejYpI_Mc
    def findBestValue1(self, arr: List[int], target: int) -> int:
        arr.sort()
        length = len(arr)
        for n in arr:
            # round is different to //. round(1.2) = 1, round(1.6) = 2
            res = round(target / length)
            if n >= res:
                return res
            target -= n
            length -= 1
        # return biggest num
        return arr[-1]


# Notice that the answer is not neccessarily a number from arr.


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        def helper(num):
            new_sum = sum([num if i > num else i for i in arr])
            return new_sum

        # right is max(arr) because change all the integers larger than value in the given array to be equal to value
        left, right = 0, max(arr)
        while left < right:
            mid = left + (right - left) // 2
            # need helper(mid) to be as close to target as possible (in absolute difference)
            if helper(mid) < target:
                left = mid + 1
            elif helper(mid) >= target:
                right = mid

        if abs(helper(left) - target) < abs(helper(left-1) - target):
            return left
        else:
            return left-1


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        #brute force, linear scan, TIME LIMIT EXCEEDED
        '''
        sums = []
        for i in range(max(arr)+1):
            currSum = 0 
            for val in arr: 
                if val > i: 
                    currSum += i
                else:
                    currSum += val
            
            sums.append((abs(currSum-target),i))
        sums.sort(key = lambda x:x[0])
        return sums[0][1]
        '''
        
        #linear scan with stopping condition, works! but really bad lol 
        '''
        sums = []
        for i in range(max(arr)+1):
            currSum = 0 
            for val in arr: 
                if val > i: 
                    currSum += i
                else:
                    currSum += val
            if currSum-target > 0:
                sums.append((abs(currSum-target),i))
                break
            else:
                sums.append((abs(currSum-target),i))
        sums.sort(key = lambda x:x[0])
        return sums[0][1]
        '''
        
        #binary search, find the minimum integer that meets stopping condition
        #since you are trying to minimize the difference, stop on the smallest one and find the corresponding value 
        '''
        def condition(cutoff): 
            currSum = 0
            for val in arr: 
                if val > cutoff: 
                    currSum += cutoff
                else:
                    currSum += val
            return abs(currSum - target)
            
        left, right = 0, target
        currSum = (float('inf'), -1) #smallest sum, the cutoff value which gives you the smallest sum 
        while left <= right: 
            mid = left + (right - left) // 2
            checkSum = condition(mid)
            if checkSum < currSum[0]: #if the smallest sum is smaller than the previous smallest sum, store the cutoff value
                currSum = (checkSum, mid)
                right = mid - 1
            else:
                left = mid + 1
            print(left, right)
        return currSum[1]
        '''
        #binary search but look for the cutoff point
        def condition(cutoff): 
            currSum = 0
            for val in arr: 
                if val > cutoff: 
                    currSum += cutoff
                else:
                    currSum += val
            return currSum   
        
        left, right = 0, max(arr)
        while left < right: 
            mid = left + (right - left) // 2
            if condition(mid) < target:
                left = mid + 1
            else:
                right = mid 

        if abs(target-condition(left)) < abs(target-condition(left-1)): 
            return left
        else:
            return left - 1
        
        
        


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        vals = sorted(arr)
        l = len(vals)
            
        diff = float('inf')
        num = -1
        m = vals[-1]
        i = 0
        prev_sum = 0 
        for n in range(m+1):
            if n > target:
                break
            
            while n > vals[i]:
                prev_sum += vals[i]
                i += 1
                    
            total = (n * (l-i)) + prev_sum
            new_diff = abs(target - total)
            if new_diff < diff:
                diff = new_diff
                num = n
                
        
        return num
                
            
            


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr = sorted(arr)
        total = sum(arr)
        if total <= target:
            return arr[-1]

        min_num = target // len(arr)
        if min_num <= arr[0]:
            below = len(arr) * min_num
            above = len(arr) * (min_num + 1)

            if abs(target - below) <= abs(target - above):
                return min_num
            else:
                return min_num + 1
        return self.findBestValue(arr[1:], target - arr[0])

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        left, right = 0, max(arr)
        
        while left <= right:
            mid = (left + right) >> 1
            count = sum([min(x, mid) for x in arr])
            if count < target:
                left = mid + 1
            else:
                right = mid - 1
        
        res1 = sum([min(x, left) for x in arr])
        res2 = sum([min(x, right) for x in arr])
        return left if abs(res1-target) < abs(res2-target) else right

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
       
        
        # sum_of_mutate(arr, sorted_arr[i]) will be like
        # L L L L M M
        # where L = sum_of_mutate[i] less than or equal target, M = more
        # we want to find last L
        # then answer can be last L or next M whatever make mutate sum smaller
        
        l = 0
        r= max(arr)
        
        while l < r:
            mid = ((l+r) // 2 ) + 1

            if self.sum_of_mutate(arr, mid) > target:
                r = mid - 1
            else:
                l = mid
        if abs(self.sum_of_mutate(arr, l) - target) <=  abs(self.sum_of_mutate(arr, l+1) - target):
            return l
        else:
            return l + 1


    def sum_of_mutate(self, arr, k):
        return sum(min(e, k) for e in arr)
        
        


class Solution:
    def findBestValue(self, A, target):
        
        def mutedSum(A, t):
            s = 0
            for x in A:
                s += min(x, t)
            return s
        
        l, r = 1, max(A)
        while l < r:
            m = (l+r) // 2
            cur = 0
            for x in A:
                cur += min(x, m)
            if cur <= target:
                l = m+1
            else:
                r = m
        
        s1 = mutedSum(A, r)
        s2 = mutedSum(A, r-1)
        return r if abs(target-s1) < abs(target-s2) else r-1
        
        
        
        
        


class Solution:
    def check(self, arr, val):
        result = 0
        for value in arr:
            result += min(value, val)
        return result
        
    def findBestValue(self, arr: List[int], target: int) -> int:
        hi = max(arr)
        lo = 0
        mid = (lo+hi) // 2
        
        limit = hi
        low_value = abs(self.check(arr, hi) - target)
        
        while lo <= hi:
            calculated_value = self.check(arr, mid)
            if calculated_value >= target:
                hi = mid - 1
                
            if calculated_value <= target:
                lo = mid + 1
                
            diff = abs(calculated_value - target)
            if diff < low_value or (diff == low_value and mid < limit):
                limit = mid
                low_value = diff
                
                
            mid = (hi + lo) // 2
            
                
        return limit


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
       
        
        # sum_of_mutate(arr, sorted_arr[i]) will be like
        # L L L L M M
        # where L = sum_of_mutate[i] less than or equal target, M = more
        # we want to find last L
        # then answer can be last L or next M whatever make mutate sum smaller
        
        l = 0
        r = max(arr)
        
        while l < r:
            mid = ((l+r) // 2 ) + 1

            if sum(min(e, mid) for e in arr) > target:
                r = mid - 1
            else:
                l = mid
                
        # then answer can be last L or next M whatever make mutate sum smaller
        # use less or equal because if it ties, we will choose smaller 
        if abs(sum(min(e, l) for e in arr)- target) <=  abs(sum(min(e, l+1) for e in arr) - target):
            return l
        else:
            return l + 1

        
        


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        #brute force, linear scan, TIME LIMIT EXCEEDED
        '''
        sums = []
        for i in range(max(arr)+1):
            currSum = 0 
            for val in arr: 
                if val > i: 
                    currSum += i
                else:
                    currSum += val
            
            sums.append((abs(currSum-target),i))
        sums.sort(key = lambda x:x[0])
        return sums[0][1]
        '''
        
        #linear scan with stopping condition, works! but really bad lol 
        '''
        sums = []
        for i in range(max(arr)+1):
            currSum = 0 
            for val in arr: 
                if val > i: 
                    currSum += i
                else:
                    currSum += val
            if currSum-target > 0:
                sums.append((abs(currSum-target),i))
                break
            else:
                sums.append((abs(currSum-target),i))
        sums.sort(key = lambda x:x[0])
        return sums[0][1]
        '''
        
        #binary search, find the minimum integer that meets stopping condition
        #since you are trying to minimize the difference, stop on the smallest one and find the corresponding value 
        '''
        def condition(cutoff): 
            currSum = 0
            for val in arr: 
                if val > cutoff: 
                    currSum += cutoff
                else:
                    currSum += val
            return abs(currSum - target)
            
        left, right = 0, target
        currSum = (float('inf'), -1) #smallest sum, the cutoff value which gives you the smallest sum 
        while left <= right: 
            mid = left + (right - left) // 2
            checkSum = condition(mid)
            if checkSum < currSum[0]: #if the smallest sum is smaller than the previous smallest sum, store the cutoff value
                currSum = (checkSum, mid)
                right = mid - 1
            else:
                left = mid + 1
            print(left, right)
        return currSum[1]
        '''
        #binary search but look for the cutoff point
        def condition(cutoff): 
            currSum = 0
            for val in arr: 
                if val > cutoff: 
                    currSum += cutoff
                else:
                    currSum += val
            return currSum   
        
        left, right = 0, max(arr)
        while left < right: 
            mid = left + (right - left) // 2
            if condition(mid) < target:
                left = mid + 1
            else:
                right = mid 

        return left if abs(target-condition(left)) < abs(target-condition(left-1)) else left-1
           
        
        
        


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        if sum(arr) <= target: return max(arr)
        lo = 0
        hi = target
        
        best = float('inf')
        res = float('inf')
        
        while lo < hi:
            mid = (lo + hi) // 2
            s = sum(min(x, mid) for x in arr)
            diff = abs(s-target)
            if diff < best or (diff == best and mid < res):
                res = mid
                best = diff

            if s > target:
                hi = mid
            else:
                lo = mid + 1
        
        return res


class Solution:
    
    def delta (self, val: int,arr: List[int], target: int) -> int:
            total = 0 
            
            for a in arr:
                if (a < val):
                    total += a 
                else:
                    total += val
            
            return (abs(total-target))
        
        
            
    def check(self, val: int,arr: List[int], target: int) -> bool:
            
            if ((self.delta(val, arr, target)-self.delta(val+1, arr, target))<=0):
                return True
            else: 
                return False
            
            
    def findBestValue(self, arr: List[int], target: int) -> int:
        
        lo = 0
        hi= sum(arr)
        
        while(lo<hi):
            
            mid = lo +((hi-lo)//2)  
                
            if (self.check(mid, arr, target)):
                hi = mid 
            else: 
                lo = mid +1
            
        
        if (self.check(lo, arr, target)):
                return lo 
        else : 
            return (0)

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        sum1=sum(arr)
        low=0
        min1=[float('Inf')]
        ans=[0]
        def check(mid,target):
            sum1=0
            for i in arr:
                if i>mid:
                    sum1+=mid
                else:
                    sum1+=i
            
               
            return sum1
        
        def binary(low,high,target):
            mid=(low+high)//2
           
            if low>high:
                return 
            x=check(mid,target)
            
            if x<target:
                
                if abs(target-x)<min1[0]:
                    ans[0]=mid
                   
                    min1[0]=abs(target-x)
                if abs(target-x)==min1[0]:
                    ans[0]=min(mid,ans[0])
                binary(mid+1,high,target)
            else:
                if abs(target-x)<min1[0]:
                    ans[0]=mid
                    min1[0]=abs(target-x)
                elif abs(target-x)==min1[0]:
                    ans[0]=min(mid,ans[0])
                
                binary(low,mid-1,target)
        binary(low,max(arr),target)
        return ans[0]

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        low = 0 
        high = (1 << 32)
        closest_diff = None
        closest_index = None
        while ((high - low) > 1):
            mid = (high + low) // 2
            mid_val = self.helper(arr,mid)
            if (closest_diff == None) or (closest_diff > abs(target - mid_val)):
                closest_index = mid
                closest_diff = abs(target - mid_val)
            elif (closest_diff == abs(target - mid_val) and mid < closest_index):
                closest_index = mid
                closest_diff = abs(target - mid_val)
                
            print(high,low,mid,self.helper(arr,mid),closest_index)

            if (mid_val < target) and (mid <= arr[len(arr) - 1]):
                low = mid
            else:
                high = mid
                
        high_val = self.helper(arr,high)
        if (closest_diff == None) or (closest_diff > abs(target - high_val)):
            closest_index = high
            closest_diff = abs(target - high_val)
        low_val = self.helper(arr,low)
        if (closest_diff == None) or (closest_diff > abs(target - low_val)):
            closest_index = low
            closest_diff = abs(target - low_val)
        elif (closest_diff == low_val and low < closest_index):
            closest_index = low
            closest_diff = abs(target - low_val)
        return closest_index
    
    def helper(self,arr,val):
        curr_sum = 0
        for num in arr:
            if num < val:
                curr_sum += num
            else:
                curr_sum += val
        return curr_sum

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        def calculate(value):
            s = 0
            for x in arr:
                s += min(x, value)
            
            return s
        
        l, r = 1, max(arr)
        while l <= r:
            mid = l + (r - l) // 2
            if calculate(mid) < target:
                l = mid + 1
            else:
                r = mid - 1
        
        if abs(calculate(l - 1) - target) <= abs(calculate(l) - target):
            return l - 1
        
        return l
        


import bisect


def calc(val, arr, prefix):
    i = bisect.bisect_left(arr, val)
    return prefix[i] + (len(arr) - i) * val


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        prefix = [0]
        for i, a in enumerate(arr):
            prefix.append(prefix[i] + a)

        l, h = 0, arr[-1]
        if h * len(arr) <= target:
            return h

        while l < h - 1:
            m = (l + h) // 2
            curr = calc(m, arr, prefix)
            if curr >= target:
                h = m
            else:
                l = m

        l_d = abs(target - calc(l, arr, prefix))
        h_d = abs(target - calc(h, arr, prefix))

        if l_d <= h_d:
            return l
        else:
            return h


class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        # 
        if not arr:
            return 0
        if len(arr) == 1:
            return arr[0] if arr[0] <= target else target
        value = 1
        sum_up = 0
        index = 0
        last_sum = 0
        arr.sort()
        while value < arr[-1]:
            
            current_sum = 0
            while value >= arr[index]:
                sum_up += arr[index]
                index += 1
            current_sum =  sum_up + ((len(arr) - index) * value)
            if current_sum == target:
                return value
            elif current_sum > target:
                if abs(last_sum - target) <= abs(current_sum - target):
                    return value - 1
                else:
                    return value
            else:
                last_sum = current_sum
            value += 1            
            
        return value

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        nums = [-x for x in arr]
        heapify(nums)
        currSum = sum(arr)
        N = len(nums)
        
        bestVal = -nums[0]
        bestDifference = float('inf')
        
        def testValue(value):
            sumWithIdeal = currSum + numElementsToChange * value
            difference = abs(target - sumWithIdeal)
            if value <= nextLargest and value >= (-nums[0] if nums else 0):
                if difference < bestDifference:
                    return int(value), abs(target - sumWithIdeal)
                elif difference == bestDifference:
                    return min(bestVal, int(value)), bestDifference
            return bestVal, bestDifference
                        
        while nums:
            nextLargest = -heappop(nums)
            currSum -= nextLargest
            numElementsToChange = N - len(nums)
            if currSum <= target:
                idealValue = (target - currSum) / numElementsToChange
                if idealValue.is_integer():
                    bestVal, bestDifference = testValue(idealValue)
                else:
                    bestVal, bestDifference = testValue(floor(idealValue))
                    bestVal, bestDifference = testValue(ceil(idealValue))
                    
        return bestVal