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 ordervoid 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 Codeint 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 approachimport java.util.*; class GFG{ // Function to count minimum anti-// clockwise rotations required to// sort the array in non-increasing orderstatic 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 Codepublic 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 orderdef 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 arrayarr = [ 2, 1, 5, 4, 2 ]N = len(arr) # Function CallminMovesToSort(arr, N)# This code is contributed by sanjoy_62. |
C#
// C# program for the above approachusing System; class GFG{ // Function to count minimum anti-// clockwise rotations required to// sort the array in non-increasing orderstatic 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 Codepublic 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 orderfunction 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 arraylet arr = [2, 1, 5, 4, 2];let N = arr.length; // Function CallminMovesToSort(arr, N);</script> |
Output:
2
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!
