Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Examples

Approach

2.1.

Steps of Algorithm

Implementation in C++

3.1.

Complexity Analysis

FAQs

Key takeaways

Last Updated: Mar 27, 2024

Reduce array to longest sorted array possible by removing either half of given array in each operation

Q: 1.What is the alternate of the ‘is_sorted’ function, which we have created manually in the code?

Ans. There is one inbuilt function in C++, which takes starting and ending iterator of the array as input, and tells us about the sorted nature of the array passed. The name of the function is ‘is_sorted()’.

Q: 2.Why are we calculating the middle element by adding half of the start and end index difference to the start index?

Ans. We are doing this because if the value of ‘N’ is too high, then adding two big numbers will go beyond the limits, and then dividing it with 2 will lead to the crisis in the code if we will calculate the middle element as follows:

Q: 3.What is a sorted array?

Ans. The array in which all the elements are in non-decreasing order is known as the sorted array.

Author Harsh Goyal

Do you think IIT Guwahati certified course can help you in your career?

Yes

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:

Output:

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:

Output:

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,

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.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
bool is_sorted(int input[], int start, int end)
{
    for(int i = start + 1; i <= end; i++)
    {
        // If elements are in decreasing order then it means that array is not sorted
        if(input[i] < input[i - 1])
        {
            return false;
        }
    }
    return true;
}

int getResult(int input[], int start , int end)
{
   // When size of the array becomes 1
   if (start >= end)
   {
       return 1;
   }

   // If the subarray is sorted
   if (is_sorted(input, start, end))
   {
       int res = end - start;
       return (res + 1);
   }

   // Mid element of the array
   int mid = start + (end - start) / 2;

   // Partitioning the array
   int first = getResult(input, start, mid);
   int second = getResult(input, mid + 1, end);

   int result = first > second ? first : second;
   return result;
}

int main()
{

   int input[] = { 10, 11, 5, 4, 6, 8, 9, 15};
   int n = sizeof(input) / sizeof(input[0]);
   cout << "Input array is:- ";
   for(int i = 0 ; i < n ; i++)
   {
       cout << input[i] << ", ";
   }
   cout << endl;
   cout << "Length Of Longest Sorted Array Possible is:- ";
   cout << getResult(input, 0, n) << endl;

   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output :

Input array is:- 10, 11, 5, 4, 6, 8, 9, 15, 
Length Of Longest Sorted Array Possible is:- 4

Complexity Analysis

Time Complexity: O(N * log N)

Incall to ‘getResult()’, we are checking the sorted nature of the array, which takes O(N) time, and after dividing the array using mid element and checking the whole array, the overall time complexity is O(N * log N), where ‘N’ is the size of the ‘input’ vector.

Space Complexity: O(1)

As we are using constant extra space, therefore, the overall space complexity will be O(1).

FAQs

1.What is the alternate of the ‘is_sorted’ function, which we have created manually in the code?

Ans. There is one inbuilt function in C++, which takes starting and ending iterator of the array as input, and tells us about the sorted nature of the array passed. The name of the function is ‘is_sorted()’.

2.Why are we calculating the middle element by adding half of the start and end index difference to the start index?

Ans. We are doing this because if the value of ‘N’ is too high, then adding two big numbers will go beyond the limits, and then dividing it with 2 will lead to the crisis in the code if we will calculate the middle element as follows:

Mid = (start + end) / 2

But if we will calculate the middle element as follows:

Mid = start + (end - start) / 2

In this way, we are adding a comparatively smaller number to ‘start’, which will give us an accurate result.

3.What is a sorted array?

Ans. The array in which all the elements are in non-decreasing order is known as the sorted array.

Key takeaways

In this article, we discussed to reduce array to the longest sorted array possible by removing either half of a given array in each operation problem and the approach to solve this problem programmatically, the time and space complexities.

Recommended Problem - Merge K Sorted Arrays

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.