Header Ad

HackerEarth Erasing an array problem solution

In this HackerEarth Erasing an Array problem solution you are given a binary array A of N elements. The array consists of 0's and 1's. You can perform the following operations as many times as possible:
  1. Select a subarray starting from the first index that is inversion-free and delete it.
  2. Determine the minimum number of operations to delete the entire array.
Inversion free: There are no two indices i and j in array A such that (i < j) and (Ai > Aj). 
Subarray: A subarray is an array obtained after deleting some elements from the beginning (prefix) possibly 0 and deleting some elements from the end (suffix) possibly 0.


hackerEarth Erasing an array problem solution


HackerEarth Erasing an array problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
int main() {
FIO;
test
{
ll n; cin>>n;
vector<ll>a(n);
for(auto &it:a) cin>>it;
int ans=0,ind=0;
while(ind<n){
ans++;
while(ind<n && a[ind]==0){
ind++;
}
while(ind<n && a[ind]==1){
ind++;
}
}
cout<<ans<<endl;
}
return 0;
}

second solution

t = int(input())
while t > 0:
t -= 1
n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in range(n - 1):
ans += a[i] - a[i + 1] == 1
print(ans)


Post a Comment

0 Comments