shah_entrance's blog

Minimum number of operation to sort an array
By shah_entrance, history, 5 years ago, In English

Given an array. Find the minimum number of operation to sort the array. Operation: Take element from any position of the array and put it to end.

  • Vote: I like it
  • -7
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For each element of the array, calculate what would its position be if we sort the array (let pos[i] be the position of element i in a sorted array). Then, find the maximum value x such that all the elements which have pos <= x are sorted (for example, let the array be [3, 4, 1, 2, 5]. Maximum x = 2 because 1 and 2 are sorted (2 is behind 1), but 3 is before 1 and 2 (so 1, 2 and 3 are not sorted)). In the end you just put all the other elements to the end of the array (in the correct order, of course). So, minimum number of operations is N (number of elements in the array) — x.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain to me for this example [6,1,3,2,5,4] ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For that example, x = 2 because numbers 1 and 2 are "sorted" (1 is before 2 in the array), but 3 is before 2 so 1, 2 and 3 are not "sorted". So the answer is 4 (you put 3, 4, 5 and 6 to the end of the array).

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
solve(vector<int>arr){
int st=0;
vector<int>v;
v=arr;
int ans=0;
int n=v.size();
sort(v.begin(),v.end());
for(int i=0;i<n;i++){
int req=v[i];
while(st<n && arr[st]!=req){
st++;
ans++;
}
st++;
if(st>=n){
break;
}
}
return ans;
}
→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had made this question for a round on CodeChef. Here is the editorial.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    recently i have given an Online Assessment in which i have been asked same question with a little change Given an array of distinct elements, you need to sort it in non-decreasing order using only two operations:

    Take an element and move it to the start.
Take an element and move it to the end.

    please help. thank you

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      Im not sure, but that could work:

the solution is similar for [this comment](https://mirror.codeforces.com/blog/entry/68102?#comment-524186), but in this comment you count sort pref in a

in my solution for each 0<=i<=n you count:

pref_ans - sort in a[0:i]

suf_ans - sort in a[i+1:n], but we starting with i(suf_sort(3) [1 3 5 4]=2)

and ans=n-pref_ans-suf_ans;

for example:

[3 1 4 2]

for i=0: pref_ans=0; suf_ans=2; ans=2;

for i=1: pref_ans=0; suf_ans=0; ans=4;

for i=2: pref_ans=1; suf_ans=0; ans=3;


for i=3: pref_ans=1; suf_ans=0; ans=3;

for i=4: pref_ans=2; suf_ans=0; ans=2;

final_ans=min(all ans)=2
      → Reply