ENCDNOV-Editorial

PROBLEM LINK:

Practice
Contest
Author: Shloka Mahesheka
Tester: Sunita Sen, Sandeep Singh, Arnab Chanda
Editorialist: Shloka Mahesheka

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sorting

PROBLEM:

Given an array of integers.
Find the minimum length subarray such that sorting this subarray makes the whole array sorted.

EXPLANATION:

We sort the copy of the given array and compare it with the original array.
By comparing the elements of the sorted array and the original array from the beginning, we find the first element that does not match and store it in variable l.
Similarly, we compare the sorted array and original array from the end and find the first element that does not match and store it in variable r.
The difference between l and r+1 is the minimum length.

TIME COMPLEXITY:

Due to the sorting of the array, Time Complexity is O(nlogn).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

int f1(vector<int> nums)
{
    vector<int> v;
        for(int i=0;i<nums.size();++i)
        {
            v.push_back(nums[i]);
        }
        sort(v.begin(),v.end());
        int l=0,h=0;
        for(int i=0;i<v.size();++i)
        {
            if(v[i]!=nums[i])
            {
                l=i;
                i=v.size();
            }
        }
        for(int i=v.size()-1;i>=0;--i)
        {
            if(v[i]!=nums[i])
            {
                h=i;
                i=-1;
            }
    
        }
   
        if(l==h)
            return 0;
        return((h-l+1));
}
int main() {
    // your code goes here
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int> a;
        for(int i=0;i<n;++i)
        {
            int x;
            cin>>x;
            a.push_back(x);
        }
        cout<<f1(a)<<"\n";
    }
 
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ln cout << '\n'
#define mod 1000000007
#define MxN 100005
#define all(x) x.begin(), x.end()
using namespace std;


void solve(){

	int i, j, n;
	cin >> n;
	vector <int> arr(n), tmp(n);

	for(i = 0; i < n; ++i){
     	cin >> arr[i];
     	tmp[i] = arr[i];
	}

	sort(all(tmp));
	int start = 0, end = n - 1;

	while(start < n && arr[start] == tmp[start])
    	++start;

	if(start == n)
    	cout << 0 << '\n';
	else{
    	while(tmp[end] == arr[end])
        	--end;
    
    	cout << end - start + 1 << endl;
    	//cout << start <<" " << end << endl;
	}



}
int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);

	#ifndef ONLINE_JUDGE
    	freopen("input.txt","r",stdin);
	#endif

	int t = 1;
	cin >> t;
	while(t--)
    	solve();
}	 
2 Likes