Amazon OA Question | 2025 | Find minimum number of operations required to convert every element of this array to 0
raunit - in CodingYou 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 sizen
.
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
-
Initialization:
- Set
ans = |v[n-1]|
(absolute value of the last element). - Set
last = v[n-1]
(tracks the value of the current prefix).
- Set
-
Iterate from Right to Left:
-
For each element
v[i]
, compare it withlast
:- Case 1:
v[i] >= last
:- Update
ans = ans + (v[i] - last)
. - Set
last = v[i]
.
- Update
- Case 2:
v[i] < last
:- Update
ans = ans + (last - v[i])
. - Set
last = v[i]
.
- Update
- Case 1:
-
For each element
-
Return
ans
:- After processing all elements,
ans
contains the minimum operations required.
- After processing all elements,
Dry Run with Example
Input:
arr = [3, 2, 1]
Dry Run Steps:
-
Initialization:
ans = 1
(absolute value ofv[2]
).last = 1
.
-
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
.
- At index 1 (
-
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;
}
raunit
Technical Writer at CodingKaro