Given an array arr[] consisting of the first N natural numbers, the task is to find the minimum number of subarrays required to be rearranged such that the resultant array is sorted.
Examples:
Input: arr[] = {2, 1, 4, 3, 5}
Output: 1
Explanation:
Operation 1: Choose the subarray {arr[0], arr[3]}, i.e. { 2, 1, 4, 3 }. Rearrange the elements of this subarray to {1, 2, 3, 4}. The array modifies to {1, 2, 3, 4, 5}.Input: arr[] = {5, 2, 3, 4, 1}
Output: 3
Approach: The given problem can be solved by observing the following scenarios:
- If the given array arr[] is already sorted, then print 0.
- If the first and the last element is 1 and N respectively, then only 1 subarray either arr[1, N – 2] or arr[2, N – 1] needs to be sorted. Therefore, print 1.
- f the first and the last element is N and 1 respectively, then 3 subarrays i.e., arr[0, N – 2], arr[1, N – 1], and arr[0, 1] need to be sorted. Therefore, print 3.
- Otherwise, sort the two subarrays i.e., arr[1, N – 1], and arr[0, N – 2].
Therefore, print the count of minimum number of subarrays required to be rearranged.
Below is the implementation of the above approach:
C++
// 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 arrayvoid 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 Codeint main(){ int arr[] = { 5, 2, 3, 4, 1 }; int N = sizeof(arr) / sizeof(arr[0]); countSubarray(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function that returns 0 if a pair// is found unsortedstatic 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 arraystatic 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 Codepublic 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
# Python3 program for the above approach# Function to count the number# of subarrays required to be# rearranged to sort the given arraydef 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 Codearr = [ 5, 2, 3, 4, 1 ]N = len(arr)countSubarray(arr, N)# This code is contributed by amreshkumar3 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function that returns 0 if a pair// is found unsortedstatic 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 arraystatic 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 Codepublic static void Main() { int []arr = { 5, 2, 3, 4, 1 }; int N = arr.Length; countSubarray(arr, N);} }// This code is contributed by bgangwar59 |
Javascript
<script>// Javascript program for the above approach// Function that returns 0 if a pair// is found unsortedfunction 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 arrayfunction 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 Codevar arr = [ 5, 2, 3, 4, 1 ];var N = arr.length;countSubarray(arr, N); // This code is contributed by SURENDRA_GANGWAR</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
