Friday, December 9, 2022
HomeSoftware DevelopmentReduce given operations required to kind the stream array

Reduce given operations required to kind the stream array


Given an array stream of n integers within the type of a stream, the duty is to seek out the minimal variety of operations which might be required to kind the stream (growing order) following the under steps:

  • In a single operation you’ll be able to choose up the primary ingredient after which put that ingredient to the xth index. 
  • All the weather to the left of the xth index shift one place left and the primary ingredient go to the following place. 
  • The place of the weather on the appropriate of the xth place stays unchanged.
  • One can select totally different x independently for various parts. 

Examples:

Enter: n = 5, stream[] = {4, 2, 3, 5, 6}
Output: 1
Explaination: Within the preliminary stream we are able to entry solely the primary ingredient which is 4 on this case and seHend it to x = 2 positions again on account of which the quantity 2 within the stream will come at first place. The brand new stream turns into {2, 3, 4, 5, 6} which is already sorted in growing order. Therefore we require 1 operation.

Enter: n = 4, stream[] = {2, 3, 5, 4}
Output: 3
Explaination: In first step we select x = 2 for first ingredient and the brand new stream turns into {3, 5, 2, 4}. In second step we select x = 2 for first ingredient and the brand new stream turns into {5, 2, 3, 4}. Within the third step we select x = 4 for first ingredient and the brand new stream turns into {2, 3, 4, 5} which is sorted. Therefore we require 3 operations.

Strategy: The given downside could be solved through the use of a small statement.

Observations:

We all the time wish to choose up the primary ingredient and put it in a spot such that the suffix of the array stays sorted. Therefore we traverse from the final ingredient of the array and discover the size of the longest suffix that’s sorted within the preliminary array. Now for every remaining ingredient aside from these within the longest sorted suffix we might require an operation. Therefore, the ultimate outcome could be n – size of the longest sorted suffix.

Comply with the steps to unravel the issue:

  • Initialize a variable say rely equal to 1. This variable shops the size of the longest sorted suffix.
  • Begin iterating the array from the second final ingredient.
  • Verify for situations whether or not the present ingredient is lower than or equal to the ingredient on its proper or not.
  • If the situation is true, increment rely by 1 (rely = rely + 1).
  • If the situation is fake, break from the loop.
  • The last result’s n – rely.

Under is the implementation of the above method:

C++

#embrace <bits/stdc++.h>

utilizing namespace std;

 

int minOpsToSort(int stream[], int n)

{

 

    

    

    

    

    int rely = 1;

    for (int i = n - 2; i >= 0; i--) {

        if (stream[i] <= stream[i + 1]) {

            rely++;

        }

        else {

            break;

        }

    }

    return n - rely;

}

 

int foremost()

{

 

    

    int stream[] = { 2, 3, 5, 4 };

    int n = sizeof(stream) / sizeof(stream[0]);

    int minimumOperations = minOpsToSort(stream, n);

   

    

    cout << minimumOperations;

    return 0;

}

Java

 

import java.io.*;

 

class GFG {

 

  

  

  public static int minOpsToSort(int[] stream, int n)

  {

 

    

    

    

    

    int rely = 1;

    for (int i = n - 2; i >= 0; i--) {

      if (stream[i] <= stream[i + 1]) {

        rely++;

      }

      else {

        break;

      }

    }

    return n - rely;

  }

 

  

  public static void foremost (String[] args)

  {

     

    

    int[] stream = { 2, 3, 5, 4 };

    int n = stream.size;

    int minimumOperations = minOpsToSort(stream, n);

 

    

    System.out.println(minimumOperations);

  }

}

 

Time Complexity: O(N) 
Auxiliary Area: O(1)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

two × 5 =

Most Popular

Recent Comments