FastPrep

Description

Solutions

Minimum Steps to Reduce Array Elements to 0

🔥 FULLTIME👩‍🎓 NEW GRAD📚RELATED PROBLEMS

You are given an integer array, and your task is to perform a series of operations to make all elements in the array equal to 0.

Operation Details:

In one operation, you can select any prefix of the array.

You can then increment or decrement all elements in the selected prefix by 1.

You are given an array arr consisting of n integers. Your task is to determine the minimum number of operations required to convert every element in the array to 0.

A prefix is defined as a contiguous group of items that includes the first element in the cart. For example, [1], [1, 2], [1, 2, 3] etc are prefixes of [1, 2, 3, 4, 5].

It is guaranteed that it is always possible to convert every element of the given array to 0 using the allowed operations.

✎﹏Credit to ⟡ Sndix ⟡ 🦋

Example 1:

Input:  arr = [3, 2, 1]
Output: 3 
Explanation:
For the input arr, the most efficient approach is:

Operation 1: Let the prefix length be 2, and decrement by 1. Cart after this operation is [2, 1, 1]

Operation 2: Let the prefix length be 1, and decrement by 1. Cart after this operation is [1, 1, 1]

Operation 3: Let the prefix length be 3, and decrement by 1. Cart after this operation is [0, 0, 0]

So the enswer is 3.

Note that it is not possible to make all the elements of the arry 0 in fewer operations.

Constraints:

Unknown for now