Count rotations required to sort given array in non-increasing order

0 0 5 minutes read

Given an array arr[] consisting of N integers, the task is to sort the array in non-increasing order by minimum number of anti-clockwise rotations. If it is not possible to sort the array, then print “-1”. Otherwise, print the count of rotations.

Examples:

Input: arr[] = {2, 1, 5, 4, 3}
Output: 2
Explanation: Two anti-clockwise rotations are required to sort the array in decreasing order, i.e. {5, 4, 3, 2, 1}

Input: arr[] = {2, 3, 1}
Output: -1

Approach: The idea is to traverse the given array arr[] and count the number of indices satisfying arr[i + 1] > arr[i]. Follow the steps below to solve the problem:

Store the count of arr[i + 1] > arr[i] in a variable and also store the index when arr[i+1] > arr[i].
If the value of count is N – 1, then the array is sorted in non-decreasing order. The required steps are exactly (N – 1).
If the value of count is 0, then the array is already sorted in non-increasing order.
If the value of count is 1 and arr[0] ? arr[N – 1], then the required number of rotations is equal to (index + 1), by performing shifting of all the numbers upto that index. Also, check if arr[0] ? arr[N – 1] to ensure if the sequence is non-increasing.
Otherwise, it is not possible to sort the array in non-increasing order.

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 minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
void minMovesToSort(int arr[], int N)
{
    // Stores count of arr[i + 1] > arr[i]
    int count = 0;
 
    // Store last index of arr[i+1] > arr[i]
    int index;
 
    // Traverse the given array
    for (int i = 0; i < N - 1; i++) {
 
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1]) {
 
            // Increment count
            count++;
 
            // Update index
            index = i;
        }
    }
 
    // Print the result according
    // to the following conditions
    if (count == 0) {
        cout << "0";
    }
    else if (count == N - 1) {
        cout << N - 1;
    }
    else if (count == 1
             && arr[0] <= arr[N - 1]) {
        cout << index + 1;
    }
 
    // Otherwise, it is not
    // possible to sort the array
    else {
        cout << "-1";
    }
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 1, 5, 4, 2 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    // Function Call
    minMovesToSort(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
   
class GFG{
   
// Function to count minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
static void minMovesToSort(int arr[], int N)
{
     
    // Stores count of arr[i + 1] > arr[i]
    int count = 0;
  
    // Store last index of arr[i+1] > arr[i]
    int index = 0;
  
    // Traverse the given array
    for(int i = 0; i < N - 1; i++) 
    {
         
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1])
        {
             
            // Increment count
            count++;
  
            // Update index
            index = i;
        }
    }
  
    // Print the result according
    // to the following conditions
    if (count == 0) 
    {
        System.out.print("0");
    }
    else if (count == N - 1)
    {
        System.out.print(N - 1);
    }
    else if (count == 1 && 
            arr[0] <= arr[N - 1]) 
    {
        System.out.print(index + 1);
    }
  
    // Otherwise, it is not
    // possible to sort the array
    else
    {
        System.out.print("-1");
    }
}
   
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int[] arr = { 2, 1, 5, 4, 2 };
    int N = arr.length;
     
    // Function Call
    minMovesToSort(arr, N);
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python program for the above approach
  
# Function to count minimum anti-
# clockwise rotations required to
# sort the array in non-increasing order
def minMovesToSort(arr, N) :
     
    # Stores count of arr[i + 1] > arr[i]
    count = 0
  
    # Store last index of arr[i+1] > arr[i]
    index = 0
  
    # Traverse the given array
    for i in range(N-1):
  
        # If the adjacent elements are
        # in increasing order
        if (arr[i] < arr[i + 1]) :
  
            # Increment count
            count += 1
  
            # Update index
            index = i
         
    # Print result according
    # to the following conditions
    if (count == 0) :
        print("0")
     
    elif (count == N - 1) :
        print( N - 1)
     
    elif (count == 1
            and arr[0] <= arr[N - 1]) :
        print(index + 1)
     
    # Otherwise, it is not
    # possible to sort the array
    else :
        print("-1")
  
# Driver Code
 
# Given array
arr = [ 2, 1, 5, 4, 2 ]
N = len(arr)
  
# Function Call
minMovesToSort(arr, N)
 
# This code is contributed by sanjoy_62.

C#

// C# program for the above approach
using System;
    
class GFG{
    
// Function to count minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
static void minMovesToSort(int[] arr, int N)
{
     
    // Stores count of arr[i + 1] > arr[i]
    int count = 0;
   
    // Store last index of arr[i+1] > arr[i]
    int index = 0;
   
    // Traverse the given array
    for(int i = 0; i < N - 1; i++) 
    {
         
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1])
        {
             
            // Increment count
            count++;
   
            // Update index
            index = i;
        }
    }
   
    // Print the result according
    // to the following conditions
    if (count == 0) 
    {
        Console.Write("0");
    }
    else if (count == N - 1)
    {
        Console.Write(N - 1);
    }
    else if (count == 1 && 
             arr[0] <= arr[N - 1]) 
    {
        Console.Write(index + 1);
    }
   
    // Otherwise, it is not
    // possible to sort the array
    else
    {
        Console.Write("-1");
    }
}
    
// Driver Code
public static void Main()
{
     
    // Given array
    int[] arr = { 2, 1, 5, 4, 2 };
    int N = arr.Length;
      
    // Function Call
    minMovesToSort(arr, N);
}
}
 
// This code is contributed by code_hunt

Javascript

<script>
 
// JavaScript program for the above approach
 
    
// Function to count minimum anti-
// clockwise rotations required to
// sort the array in non-increasing order
function minMovesToSort(arr, N)
{
     
    // Stores count of arr[i + 1] > arr[i]
    let count = 0;
   
    // Store last index of arr[i+1] > arr[i]
    let index = 0;
   
    // Traverse the given array
    for(let i = 0; i < N - 1; i++) 
    {
         
        // If the adjacent elements are
        // in increasing order
        if (arr[i] < arr[i + 1])
        {
             
            // Increment count
            count++;
   
            // Update index
            index = i;
        }
    }
   
    // Print result according
    // to the following conditions
    if (count == 0) 
    {
        document.write("0");
    }
    else if (count == N - 1)
    {
        document.write(N - 1);
    }
    else if (count == 1 && 
             arr[0] <= arr[N - 1]) 
    {
        document.write(index + 1);
    }
   
    // Otherwise, it is not
    // possible to sort the array
    else
    {
        document.write("-1");
    }
}
    
// Driver Code
 
// Given array
let arr = [2, 1, 5, 4, 2];
let N = arr.length;
  
// Function Call
minMovesToSort(arr, N);
 
 
</script>

Output:

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 zambiatek!