Minimum operations

 Problem:-

You are given an array 

A

 of length 

N

 and can perform the following operation on the array:

  • Select a subarray from array 
    A

     having the same value of elements and decrease the value of all the elements in that subarray by any positive integer 

    x

    .

Find the minimum number of operations required to make all the elements of array 

A

 equal to zero.

Input format

  • The first line contains an integer 
    N

     denoting the number of elements in the array.

  • The next line contains space-separated integers denoting the elements of array 
    A

    .

Output format

Print the minimum number of operations required to make all the elements of array 

A

 equal to zero.

Constraints

1N5×1051A[i]109

Sample Input
5
2 2 1 3 1
Sample Output
4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

  • 1st

     Operation , choose subarray [5,5] and x = 1.

    • Array 
      A

       becomes 

      [2,2,1,3,0]


  • 2nd

     Operation , choose subarray [3,3] and x = 1.

    • Array 
      A

       becomes 

      [2,2,0,3,0]


  • 3rd

     Operation , choose subarray [1,2] and x = 2.

    • Array 
      A

       becomes 

      [0,0,0,3,0]


  • 4th

     Operation , choose subarray [4,4] and x = 3.

    • Array 
      A

       becomes 

      [0,0,0,0,0]

  • Hence, minimum 
    4

     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=j1;
        ans++;
    }
    cout<<ans;
    return 0;
}



Leave a Reply

Your email address will not be published.