#Array Adjustment
'''
Given an integer array nums containing positive elements and an int maxValue.
Find the value of x such that the sum of the elements of the array is maximum
and is less than the given maxValue.
x is defined as: if the current value is greater than x, then x is used as the new value,
otherwise keep the original value nums[i] = min(x, nums[i]).

Example 1:

Input: nums = [10, 5, 20, 30], maxValue = 40
Output: 12
Explanation:
If x = 10, the array would be nums = [10, 5, 10, 10] and the sum of the array elements would be 35.
If x = 12, the array would be nums = [10, 5, 12, 12] and the sum of the elements would be 39 which is the maximum sum close to given maxValue which is 40.
So the answer would be 12.
'''
class Solution(object):
    def __init__(self):
        self.largestX = None
        
    def getNewAdjustedArray(self, nums, x):
        newArray = []
        for num in nums:
            newArray.append(min(x, num))
        return newArray

    def binarySearch(self, nums, maxValue, low, high):
        if(low > high):
            return
        mid = (low+high)/2
        newArray = self.getNewAdjustedArray(nums, mid)
        if(sum(newArray) >= maxValue):
            self.binarySearch(nums, maxValue, low, mid-1)
        else:
            # Record the mid value as highest x value
            self.largestX = mid
            self.binarySearch(nums, maxValue, mid+1, high)
        
    def getX(self, nums, maxValue):
        # From the problem we see that there is a range here,
        # at any given point we cannot change value of x to be more than the largest element
        # because of this rule nums[i] = min(x, nums[i]).
        for x in range(1, max(nums)):
            newArray = self.getNewAdjustedArray(nums, x)
            print newArray, sum(newArray)
        # from the above output we see that we can use binary search here.
        self.binarySearch(nums, maxValue, 1, max(nums))
        print self.largestX

# Main
nums = [10, 5, 20, 30]
maxValue = 40
obj = Solution()
obj.getX(nums, maxValue)