# Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.

smallest-subarray-large-than-value.py

# Given an array of integers and a number x, find the smallest subarray with sum greater than the given value.

"""
arr[] = {1, 4, 45, 6, 0, 19}
   x  =  51
Output: 3
Minimum length subarray is {4, 45, 6}
"""

save = None

def checkArray(arr, val):
  global save
  if sum(arr) > val:
    print("----HIT: ", arr, sum(arr))
    if save is None:
      print("FIRST SAVE", arr)
      save = arr
    elif len(arr) < len(save):
      print("~~~SAVE~~~", arr)
      save = arr


def smallestArray(arr, val):
  global save
  for i in range(0, len(arr)):
    tmp = [] # new subarray at each index
    for x in range(i, len(arr)):
      tmp.append(arr[x])
      checkArray(list(tmp), val) # pass a list so that the nums are immutable
  
  print("FINAL ANSWER: ", save)


# smallestArray([1, 4, 45, 6, 0, 19], 51)

smallestArray([1, 11, 100, 1, 0, 200, 3, 2, 1, 250], 280)
# smallestArray([1, 2, 4], 8)

----HIT: [1, 11, 100, 1, 0, 200] 313
FIRST SAVE [1, 11, 100, 1, 0, 200]
----HIT: [1, 11, 100, 1, 0, 200, 3] 316
----HIT: [1, 11, 100, 1, 0, 200, 3, 2] 318
----HIT: [1, 11, 100, 1, 0, 200, 3, 2, 1] 319
----HIT: [1, 11, 100, 1, 0, 200, 3, 2, 1, 250] 569
----HIT: [11, 100, 1, 0, 200] 312

----HIT:  [11, 100, 1, 0, 200, 3] 315
----HIT:  [11, 100, 1, 0, 200, 3, 2] 317
----HIT:  [11, 100, 1, 0, 200, 3, 2, 1] 318
----HIT:  [11, 100, 1, 0, 200, 3, 2, 1, 250] 568
----HIT:  [100, 1, 0, 200] 301
~~~SAVE~~~ [100, 1, 0, 200]
----HIT:  [100, 1, 0, 200, 3] 304
----HIT:  [100, 1, 0, 200, 3, 2] 306
----HIT:  [100, 1, 0, 200, 3, 2, 1] 307
----HIT:  [100, 1, 0, 200, 3, 2, 1, 250] 557
----HIT:  [1, 0, 200, 3, 2, 1, 250] 457
----HIT:  [0, 200, 3, 2, 1, 250] 456
----HIT:  [200, 3, 2, 1, 250] 456
FINAL ANSWER:  [100, 1, 0, 200]