Número de subarreglos necesarios para reorganizar para ordenar el arreglo dado

Dada una array arr[] que consta de los primeros N números naturales , la tarea es encontrar el número mínimo de subarreglos necesarios para reorganizar de manera que la array resultante esté ordenada .

Ejemplos:

Entrada: arr[] = {2, 1, 4, 3, 5}
Salida: 1
Explicación:
Operación 1: Elija el subarreglo {arr[0], arr[3]}, es decir, { 2, 1, 4, 3 } . Reorganiza los elementos de este subarreglo a {1, 2, 3, 4}. La array se modifica a {1, 2, 3, 4, 5}.

Entrada: arr[] = {5, 2, 3, 4, 1}
Salida: 3

Enfoque: El problema dado se puede resolver observando los siguientes escenarios:

• Si la array dada arr[] ya está ordenada, imprima 0 .
• Si el primer y el último elemento son 1 y N respectivamente, entonces solo se debe ordenar 1 subarreglo, ya sea arr[1, N – 2] o arr[2, N – 1] . Por lo tanto, imprima 1 .
• Si el primer y último elemento es N y 1 respectivamente, entonces se deben ordenar 3 subarreglos, es decir, arr[0, N – 2] , arr[1, N – 1] y arr[0, 1] . Por lo tanto, imprima 3 .
• De lo contrario, ordene los dos subarreglos, es decir, arr[1, N – 1] y arr[0, N – 2] .

Por lo tanto, imprima el recuento del número mínimo de subarreglos necesarios para reorganizar.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number
// of subarrays required to be
// rearranged to sort the given array
void countSubarray(int arr[], int n)
{
    // Base Case
    int ans = 2;
 
    // Check if the given array is
    // already sorted
    if (is_sorted(arr, arr + n)) {
        ans = 0;
    }
 
    // Check if the first element of
    // array is 1 or last element is
    // equal to size of array
    else if (arr[0] == 1
             || arr[n - 1] == n) {
        ans = 1;
    }
    else if (arr[0] == n
             && arr[n - 1] == 1) {
        ans = 3;
    }
 
    // Print the required answer
    cout << ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 2, 3, 4, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    countSubarray(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function that returns 0 if a pair
// is found unsorted
static int arraySortedOrNot(int arr[], int n)
{
     
    // Array has one or no element or the
    // rest are already checked and approved.
    if (n == 1 || n == 0)
        return 1;
 
    // Unsorted pair found (Equal values allowed)
    if (arr[n - 1] < arr[n - 2])
        return 0;
 
    // Last pair was sorted
    // Keep on checking
    return arraySortedOrNot(arr, n - 1);
}
 
// Function to count the number
// of subarrays required to be
// rearranged to sort the given array
static void countSubarray(int arr[], int n)
{
     
    // Base Case
    int ans = 2;
 
    // Check if the given array is
    // already sorted
    if (arraySortedOrNot(arr, arr.length) != 0)
    {
        ans = 0;
    }
     
    // Check if the first element of
    // array is 1 or last element is
    // equal to size of array
    else if (arr[0] == 1 ||
             arr[n - 1] == n)
    {
        ans = 1;
    }
    else if (arr[0] == n &&
             arr[n - 1] == 1)
    {
        ans = 3;
    }
 
    // Print the required answer
    System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, 2, 3, 4, 1 };
    int N = arr.length;
     
    countSubarray(arr, N);
}   
}
 
// This code is contributed by susmitakundugoaldanga

# Python3 program for the above approach
 
# Function to count the number
# of subarrays required to be
# rearranged to sort the given array
def countSubarray(arr, n):
     
    # Base Case
    ans = 2
     
    # Check if the given array is
    # already sorted
    if (sorted(arr) == arr):
        ans = 0
         
    # Check if the first element of
    # array is 1 or last element is
    # equal to size of array
    elif (arr[0] == 1 or arr[n - 1] == n):
        ans = 1
    elif (arr[0] == n and arr[n - 1] == 1):
        ans = 3
         
    # Print the required answer
    print(ans)
 
# Driver Code
arr = [ 5, 2, 3, 4, 1 ]
N = len(arr)
 
countSubarray(arr, N)
 
# This code is contributed by amreshkumar3

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that returns 0 if a pair
// is found unsorted
static int arraySortedOrNot(int []arr, int n)
{
     
    // Array has one or no element or the
    // rest are already checked and approved.
    if (n == 1 || n == 0)
        return 1;
 
    // Unsorted pair found (Equal values allowed)
    if (arr[n - 1] < arr[n - 2])
        return 0;
 
    // Last pair was sorted
    // Keep on checking
    return arraySortedOrNot(arr, n - 1);
}
 
// Function to count the number
// of subarrays required to be
// rearranged to sort the given array
static void countSubarray(int []arr, int n)
{
     
    // Base Case
    int ans = 2;
 
    // Check if the given array is
    // already sorted
    if (arraySortedOrNot(arr, arr.Length) != 0)
    {
        ans = 0;
    }
     
    // Check if the first element of
    // array is 1 or last element is
    // equal to size of array
    else if (arr[0] == 1 ||
             arr[n - 1] == n)
    {
        ans = 1;
    }
    else if (arr[0] == n &&
             arr[n - 1] == 1)
    {
        ans = 3;
    }
 
    // Print the required answer
    Console.Write(ans);
}
 
// Driver Code
public static void Main()
{
    int []arr = { 5, 2, 3, 4, 1 };
    int N = arr.Length;
     
    countSubarray(arr, N);
}   
}
 
// This code is contributed by bgangwar59

<script>
 
// Javascript program for the above approach
 
// Function that returns 0 if a pair
// is found unsorted
function arraySortedOrNot(arr, n)
{
     
    // Array has one or no element or the
    // rest are already checked and approved.
    if (n == 1 || n == 0)
        return 1;
 
    // Unsorted pair found (Equal values allowed)
    if (arr[n - 1] < arr[n - 2])
        return 0;
 
    // Last pair was sorted
    // Keep on checking
    return arraySortedOrNot(arr, n - 1);
}
 
// Function to count the number
// of subarrays required to be
// rearranged to sort the given array
function countSubarray(arr, n)
{
     
    // Base Case
    var ans = 2;
 
    // Check if the given array is
    // already sorted
    if (arraySortedOrNot(arr, arr.length) != 0)
    {
        ans = 0;
    }
     
    // Check if the first element of
    // array is 1 or last element is
    // equal to size of array
    else if (arr[0] == 1 ||
             arr[n - 1] == n)
    {
        ans = 1;
    }
    else if (arr[0] == n &&
             arr[n - 1] == 1)
    {
        ans = 3;
    }
 
    // Print the required answer
    document.write(ans);
}
 
// Driver Code
var arr = [ 5, 2, 3, 4, 1 ];
var N = arr.length;
 
countSubarray(arr, N);
 
// This code is contributed by SURENDRA_GANGWAR
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)