Minimum Number of Operations to Reduce Array to Zero

Do not collapse different problems into one

“Reduce array to zero” may mean decrement any positive contiguous segment, replace an element by a divisor, subtract powers of two, or repeatedly halve the entire array. Those versions are not interchangeable. First ask what an operation changes and whether it has a cost independent of length. Then seek a lower bound: for segment decrements, each newly rising height contributes an unavoidable start; for independently clearing integers by bit operations, set bits and maximum bit length often determine the count. Finally give a construction that reaches that bound.

Explain proof, not only code

For the common positive-array segment-decrement version, scan left to right and add max(0, nums[i]-nums[i-1]); each rise requires that many new operations, and starting exactly those operations achieves the result. It is O(n) time and O(1) extra space. If the operation instead reduces individual values with divide-by-two and subtract-one, count all set bits plus the highest set-bit depth, again after confirming the global operation semantics. Test zeros between positives, repeated plateaus, a single element, and an empty-array convention.