Problem:-
You are given an array of length and can perform the following operation on the array:
- Select a subarray from array having the same value of elements and decrease the value of all the elements in that subarray by any positive integer .
Find the minimum number of operations required to make all the elements of array equal to zero.
Input format
- The first line contains an integer denoting the number of elements in the array.
- The next line contains space-separated integers denoting the elements of array .
Output format
Print the minimum number of operations required to make all the elements of array equal to zero.
Constraints
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
- Operation , choose subarray [5,5] and x = 1.
- Array becomes
- Operation , choose subarray [3,3] and x = 1.
- Array becomes
- Operation , choose subarray [1,2] and x = 2.
- Array becomes
- Operation , choose subarray [4,4] and x = 3.
- Array becomes
- Hence, minimum operations are required
Code:-
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
long int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int ans=0;
for(int i=0;i<n;i++)
{
int j=i;
while(j<n && a[i]==a[j])
{
j++;
}
i=j-1;
ans++;
}
cout<<ans;
return 0;
}
0 Comments