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 (6)
| 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