We are given an elevation map, heights[i] representing the height of the terrain at that index.  The width at each index is 1.  After V units of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index.  Then, it flows according to the following rules:
If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it's current position.
Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction.
Also, "level" means the height of the terrain plus any water in that column.

We can assume there's infinitely high terrain on the two sides out of bounds of the array.  Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.


Example 1:

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
#       #
#       #
##  # ###
#########
 0123456    


Example 2:

Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.



Example 3:

Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]



Note:
heights will have length in [1, 100] and contain integers in [0, 99].
V will be in range [0, 2000].
K will be in range [0, heights.length - 1].

Difficulty: interview

Starter code:

class Solution:
    def pourWater(self, heights: List[int], V: int, K: int) -> List[int]:
        

Solutions:
def fun(k):
     n = 1 + 8*k
     s = math.floor(n**0.5)-1
     s = s//2
     return s
 class Solution:
     def reachNumber(self, target):
         """
         :type target: int
         :rtype: int
         """
         if target<0:
             target *= -1
         L = [[3,2,1,1],[1,1,3,2]] 
         k = fun(target)
         if k*(k+1)/2==target:
             ans = 0
         else:
             ans = L[target%2][k%4]
         #print(target,"->",k,k+ans)
         return k+ans
         

import math
 
 class Solution:
     def reachNumber(self, target):
         """
         :type target: int
         :rtype: int
         """
         if target < 0: target = - target
         n = math.floor((target * 2) ** 0.5)
         while n * (n + 1) < 2 * target: n += 1
         while ((n - 1) % 4) >> 1 == target % 2: n += 1
         return n

class Solution:
     def reachNumber(self, target):
         t = abs(target)
         n = math.floor(math.sqrt(2*t))
         while True:
             to_minus = ((n+1)*n)/2 - t 
             if to_minus >= 0:  
                 if to_minus%2==0:
                     return int(n)
             n+=1


class Solution:
     def reachNumber(self, target):
         """
         :type target: int
         :rtype: int
         """
         target=abs(target)
         
         n=math.ceil(((1+8*target)**0.5-1)/2)
         
         if target%2>0:
             if n%4==1 or n%4==2:
                 return n
             elif n%4==3:
                 return n+2
             else:
                 return n+1
         else:
             if n%4==3 or n%4==0:
                 return n
             elif n%4==1:
                 return n+2
             else:
                 return n+1


class Solution:
     def reachNumber(self, target):
         target = abs(target)
         def binary_search(lo, hi):
             if lo >= hi:
                 return lo
 
             mi = lo + (hi - lo) // 2
             t = mi * (mi + 1) // 2
 
             if t == target:
                 return mi
             elif t < target:
                 return binary_search(mi + 1, hi)
             else:
                 return binary_search(lo, mi)
 
         res = binary_search(0, target)
         if target % 2 == 0 and 1 <= res % 4 <= 2:
             return res + 3 - res % 4
         elif target % 2 == 1 and (res % 4 == 3 or res % 4 == 0):
             return res + 4 - (res - 1) % 4
         else:
             return res

import math
 class Solution:
     def reachNumber(self, target):
         """
         :type target: int
         :rtype: int
         """
         nTarget = target if (target>0) else -target
         n = math.ceil((-1 + math.sqrt(1+8*nTarget))/(2))
         curSum = int(n*(n+1)/2)
         if curSum == nTarget: return n
         res = curSum - nTarget
         if res%2 == 0: return n
         if n%2 == 1: return n+2
         return n+1

import math
 class Solution:
     def reachNumber(self, x):
         """
         :type target: int
         :rtype: int
         """
         if x == 0:
             return 0
 
         x = abs(x)
         n = max(math.floor(math.sqrt(2 * x)) - 1, 0)
         sum = n * (n + 1) // 2
         while sum < x:
             n += 1
             sum += n
 
         if (sum - x) % 2 == 0:
             return n
         else:
             if (n + 1) % 2 == 1:
                 return n + 1
             else:
                 return n + 2

class Solution:
     def reachNumber(self, t):
         """
         :type target: int
         :rtype: int
         """
         t = abs(t)
         lo,hi = 1,t
         while lo<hi:
             m = (lo+hi)//2
             val = m*(m+1)//2
             if val<t: lo = m+1
             else: hi = m
         sm = lo*(lo+1)//2
         ans = lo
         while (sm-t)%2!=0:
             ans += 1
             sm += ans
         return ans

class Solution:
     def reachNumber(self, target):
         """
         :type target: int
         :rtype: int
         """
         target = abs(target)
         s = 0
         for i in range( target+1):
             s += i
             if s >= target:
                 break
         if (s - target)&1 :
             if (i+1)&1:
                 return i+1
             else:
                 return i+2
         else:
             return i