Amazon OA Question | 2025 | Find minimum number of operations required to convert every element of this array to 0

raunit - in Coding
You have an array, arr consisting of n integers. Find the minimum number of operations required to convert every element of this array to zero.

Problem Statement

You are given an integer array arr, and your task is to perform operations on the array to make all its elements equal to 0.

In one operation, you can select a prefix of the array and increment or decrement all the elements of the prefix by 1.

Definition of Prefix:

A prefix is a contiguous group of elements starting from the first element of the array. For example, the prefixes of the array [1, 2, 3, 4, 5] are:

  • [1]
  • [1, 2]
  • [1, 2, 3]
  • [1, 2, 3, 4]
  • [1, 2, 3, 4, 5]

Your goal is to determine the minimum number of operations required to make every element in the array equal to 0.

Input:

  • arr: An array of integers of size n.

Output:

Return a single integer representing the minimum number of operations required to make all elements of the array 0.

Constraints:

  • 1 ≤ n ≤ 105
  • -109 ≤ arr[i] ≤ 109

Example:

Input: arr = [3, 2, 1]

The most efficient approach is:

  • Operation 1: Let the prefix length be 2, and decrement by 1. After this operation, arr = [2, 1, 1].
  • Operation 2: Let the prefix length be 1, and decrement by 1. After this operation, arr = [1, 1, 1].
  • Operation 3: Let the prefix length be 3, and decrement by 1. After this operation, arr = [0, 0, 0].

Output: 3

Code Explanation

  1. Initialization:

    • Set ans = |v[n-1]| (absolute value of the last element).
    • Set last = v[n-1] (tracks the value of the current prefix).
  2. Iterate from Right to Left:

    • For each element v[i], compare it with last:
      • Case 1: v[i] >= last:
        • Update ans = ans + (v[i] - last).
        • Set last = v[i].
      • Case 2: v[i] < last:
        • Update ans = ans + (last - v[i]).
        • Set last = v[i].
  3. Return ans:

    • After processing all elements, ans contains the minimum operations required.

Dry Run with Example

Input:

arr = [3, 2, 1]

Dry Run Steps:

  1. Initialization:

    • ans = 1 (absolute value of v[2]).
    • last = 1.
  2. Iterate from Right to Left:

    • At index 1 (v[1] = 2):
      • v[1] >= last (2 >= 1).
      • Update ans = 1 + (2 - 1) = 2.
      • Set last = 2.
    • At index 0 (v[0] = 3):
      • v[0] >= last (3 >= 2).
      • Update ans = 2 + (3 - 2) = 3.
      • Set last = 3.
  3. Final Result:

    • ans = 3.
#include <bits/stdc++.h>
using namespace std;

long long solve(vector<int>&v){
    int n = v.size();
    long long ans = abs(v[n-1]);
    int last = v[n-1];
    for(int i = n-2; i>=0; i--){
        if(last<=v[i]){
            ans -= last;
            ans += v[i];
            last = v[i];
        } else {
            ans += (last-v[i]);
            last = v[i];
        }
    }
    return ans;
}


int main() {
	int n;
	cin>>n;
	vector<int>v(n);
	for(int i = 0; i<n; i++)cin>>v[i];
	cout<<solve(v)<<endl;

}
TagsAmazonInterviewDSACP
raunit-picture
raunit

Technical Writer at CodingKaro

Share this on
Other Blogs in Coding