Given an array arr[] of size N (always power of 2), the task is to find the length of the longest sorted array to which the given array can be reduced by removing either half of the array at each operation.
Examples:
Input: arr[] = { 11, 12, 1, 2, 13, 14, 3, 4 }
Output: 2
Explanation:
Removal of the first half of arr[] modifies arr[] to {13, 14, 3, 4}.
Removal of the first half of arr[] modifies arr[] to {3, 4}.
Therefore, the length of the longest sorted array possible is 2 which is the maximum possible.Input: arr[] = { 1, 2, 2, 4 }
Output: 4
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say MaxLength, to store the maximum length of the sorted array that can be obtained by performing the given operations.
- Recursively partition the array into two equal halves and for each half, check if the partition of the array is sorted or not. If found to be true, then update MaxLength to the length of the partition.
- Finally, print the value of MaxLength.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the subarray// arr[i..j] is a sorted subarray or notint isSortedparitions(int arr[], int i, int j){ // Traverse all elements of // the subarray arr[i...j] for (int k = i + 1; k <= j; k++) { // If the previous element of the // subarray exceeds current element if (arr[k] < arr[k - 1]) { // Return 0 return 0; } } // Return 1 return 1;}// Recursively partition the array// into two equal halvesint partitionsArr(int arr[], int i, int j){ // If atmost one element is left // in the subarray arr[i..j] if (i >= j) return 1; // Checks if subarray arr[i..j] is // a sorted subarray or not bool flag = isSortedparitions( arr, i, j); // If the subarray arr[i...j] // is a sorted subarray if (flag) { return (j - i + 1); } // Stores middle element // of the subarray arr[i..j] int mid = (i + j) / 2; // Recursively partition the current // subarray arr[i..j] into equal halves int X = partitionsArr(arr, i, mid); int Y = partitionsArr(arr, mid + 1, j); return max(X, Y);}// Driver Codeint main(){ int arr[] = { 11, 12, 1, 2, 13, 14, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); cout << partitionsArr( arr, 0, N - 1); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ // Function to check if the subarray// arr[i..j] is a sorted subarray or notstatic int isSortedparitions(int arr[], int i, int j){ // Traverse all elements of // the subarray arr[i...j] for(int k = i + 1; k <= j; k++) { // If the previous element of the // subarray exceeds current element if (arr[k] < arr[k - 1]) { // Return 0 return 0; } } // Return 1 return 1;} // Recursively partition the array// into two equal halvesstatic int partitionsArr(int arr[], int i, int j){ // If atmost one element is left // in the subarray arr[i..j] if (i >= j) return 1; // Checks if subarray arr[i..j] is // a sorted subarray or not int flag = (int)isSortedparitions(arr, i, j); // If the subarray arr[i...j] // is a sorted subarray if (flag != 0) { return (j - i + 1); } // Stores middle element // of the subarray arr[i..j] int mid = (i + j) / 2; // Recursively partition the current // subarray arr[i..j] into equal halves int X = partitionsArr(arr, i, mid); int Y = partitionsArr(arr, mid + 1, j); return Math.max(X, Y);} // Driver Codepublic static void main(String[] args){ int arr[] = { 11, 12, 1, 2, 13, 14, 3, 4 }; int N = arr.length; System.out.print(partitionsArr( arr, 0, N - 1));}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program to implement# the above approach# Function to check if the subarray# arr[i..j] is a sorted subarray or notdef isSortedparitions(arr, i, j): # Traverse all elements of # the subarray arr[i...j] for k in range(i + 1, j + 1): # If the previous element of the # subarray exceeds current element if (arr[k] < arr[k - 1]): # Return 0 return 0 # Return 1 return 1# Recursively partition the array# into two equal halvesdef partitionsArr(arr, i, j): # If atmost one element is left # in the subarray arr[i..j] if (i >= j): return 1 # Checks if subarray arr[i..j] is # a sorted subarray or not flag = int(isSortedparitions(arr, i, j)) # If the subarray arr[i...j] # is a sorted subarray if (flag != 0): return (j - i + 1) # Stores middle element # of the subarray arr[i..j] mid = (i + j) // 2 # Recursively partition the current # subarray arr[i..j] into equal halves X = partitionsArr(arr, i, mid); Y = partitionsArr(arr, mid + 1, j) return max(X, Y)# Driver Codeif __name__ == '__main__': arr = [ 11, 12, 1, 2, 13, 14, 3, 4 ] N = len(arr) print(partitionsArr(arr, 0, N - 1))# This code is contributed by Princi Singh |
C#
// C# program to implement// the above approach using System; class GFG{ // Function to check if the subarray// arr[i..j] is a sorted subarray or notstatic int isSortedparitions(int[] arr, int i, int j){ // Traverse all elements of // the subarray arr[i...j] for(int k = i + 1; k <= j; k++) { // If the previous element of the // subarray exceeds current element if (arr[k] < arr[k - 1]) { // Return 0 return 0; } } // Return 1 return 1;} // Recursively partition the array// into two equal halvesstatic int partitionsArr(int[] arr, int i, int j){ // If atmost one element is left // in the subarray arr[i..j] if (i >= j) return 1; // Checks if subarray arr[i..j] is // a sorted subarray or not int flag = (int)isSortedparitions(arr, i, j); // If the subarray arr[i...j] // is a sorted subarray if (flag != 0) { return (j - i + 1); } // Stores middle element // of the subarray arr[i..j] int mid = (i + j) / 2; // Recursively partition the current // subarray arr[i..j] into equal halves int X = partitionsArr(arr, i, mid); int Y = partitionsArr(arr, mid + 1, j); return Math.Max(X, Y);} // Driver Codepublic static void Main(){ int[] arr = { 11, 12, 1, 2, 13, 14, 3, 4 }; int N = arr.Length; Console.Write(partitionsArr( arr, 0, N - 1));}}// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program to implement// the above approach// Function to check if the subarray// arr[i..j] is a sorted subarray or notfunction isSortedparitions(arr, i, j){ // Traverse all elements of // the subarray arr[i...j] for (var k = i + 1; k <= j; k++) { // If the previous element of the // subarray exceeds current element if (arr[k] < arr[k - 1]) { // Return 0 return 0; } } // Return 1 return 1;}// Recursively partition the array// into two equal halvesfunction partitionsArr(arr, i, j){ // If atmost one element is left // in the subarray arr[i..j] if (i >= j) return 1; // Checks if subarray arr[i..j] is // a sorted subarray or not var flag = isSortedparitions( arr, i, j); // If the subarray arr[i...j] // is a sorted subarray if (flag) { return (j - i + 1); } // Stores middle element // of the subarray arr[i..j] var mid = parseInt((i + j) / 2); // Recursively partition the current // subarray arr[i..j] into equal halves var X = partitionsArr(arr, i, mid); var Y = partitionsArr(arr, mid + 1, j); return Math.max(X, Y);}// Driver Codevar arr = [11, 12, 1, 2, 13, 14, 3, 4 ];var N = arr.length;document.write( partitionsArr( arr, 0, N - 1));</script> |
Output:
2
Time Complexity: O(N * log(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!
