## Introduction

This blog will discuss the approach to reduce the array to the longest sorted array possible by removing either half of the given array in each operation. Before jumping on the approach of the problem, let’s first understand the problem,

### Problem Statement

In this problem, we need to return the length of the longest possible sorted array. In each operation, we have two choices either remove half the size of the array elements from the array or keep the array as it is.

### Sample Examples

**Example 1:**

**Input:**

10 |
11 |
5 |
4 |
6 |
8 |
9 |
15 |

**Output:**

4

**Explanation:**

In this array of size 8, we can either reduce the array by half the size in each operation. As we can see that the current array is not sorted, therefore in the first operation, we divided the array into two equal parts, and then we found that the second subarray {6, 8, 9, 15} is sorted. Therefore the length of the longest sorted array is 4.

**Example 2:**

**Input:**

14 |
9 |
5 |
4 |
3 |
2 |
1 |

**Output:**

1

**Explanation:**

In this array of size 7, we can either reduce the array by half the size in each operation. As we can see that the current array is not sorted, therefore in the first operation, we divided the array into two equal parts,

14 |
9 |
5 |
4 |

3 |
2 |
1 |

In these 2 parts, we can see that both the parts are not sorted, therefore we again reduced the array by half of its size on both the halves, then after dividing the array, we can again see that the reduced arrays are not sorted, therefore, after reaching the array size of only 1, we will get maximum value as 1 which shows that the longest sorted array possible after removing either half of the given array in one operation is 1.

Also see, __Euclid GCD Algorithm__

## Approach

This approach considers checking the sorted nature of the array received from the function. If the array passed in the function is not sorted, then we need to find the middle index of the array received, and then we need to recursively divide the array into two equal parts, and then we should check for the longest sorted array. If the array received is sorted, then we need to return the length of that subarray.

### Steps of Algorithm

**Step 1**. Create a function ‘getResult()’ that will accept three parameters, i.e., one array of integer ‘input’, the second one is the ‘start’ - the start index of the array ‘input’, and the third one is the ‘end’ - the ending index of the array ‘input’.

**Step 2**. Check if the size of the array received is only 1 or not, if it is only 1, then return the size of the longest sorted array as 1.

**Step 3**. If it is not 1, then check whether the array is sorted or not by passing the array and its bounds in which we need to check its sorted nature in the inbuilt ‘is_sorted’ function.

**Step 4. **If the array is sorted, then return the size of that subarray.

**Step 5**. If the array is not sorted, then we need to calculate the middle index of the array received, divide the array into two equal halves and check for those subarrays by calling recursively.

**Step 6. **Return the maximum value received from both the recursive calls.