[LeetCode] 1413. Minimum Value to Get Positive Step by Step Sum

 Problem : https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum/

Assume x is a valid start value, then x + 1 is also a start value.

Assume x is an invalid start value, then x - 1 is also a invalid start value.

So there is a contiguous valid start value section. We can use binary search to find the lower bound of the section.

class Solution {
    fun minStartValue(nums: IntArray): Int {
    
        fun isValid(x: Int): Boolean {
            var prefixSum = x
            
            nums.forEach {
                prefixSum += it
                if (prefixSum < 1) {
                    return false
                }
            }
            
            return true
        }
        
        // valid start value section [1, nums.size * 100 + 1]
        // 1 -> when all numbers in the array equal to 0
        // nums.size * 100 + 1 -> when all numbers in the array equal to -100
        
        var left = 1
        var right = nums.size * 100 + 1
        
        while (left < right) {
            val mid = left + (right - left) / 2
            
            if (isValid(mid)) {
                right = mid
            } else {
                left = mid + 1
            }
            
        }
        
        return right
    }
}