# Count of rotations required to generate a sorted array

• Difficulty Level : Easy
• Last Updated : 10 Jun, 2021

Given an array arr[], the task is to find the number of rotations required to convert the given array to sorted form.
Examples:

Input: arr[] = {4, 5, 1, 2, 3}
Output:
Explanation:
Sorted array {1, 2, 3, 4, 5} after 2 anti-clockwise rotations.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Input: arr[] = {2, 1, 2, 2, 2}
Output:
Explanation:
Sorted array {1, 2, 2, 2, 2} after 1 anti-clockwise rotations.

Naive Approach:
To solve the problem mentioned above the first observation is if we have n elements in the array then after sorting, the largest element is at (n – 1)th position. After k number of anti-clockwise rotations, the largest element will be at index (k – 1) (kth element from start). Another thing to note here is that, after rotation, the next element of the largest element will always be the smallest element, (unless the largest element is at last index, possible if there was no rotation).
Hence,

Number of rotations (k) = index of smallest element (k) in the array

Below is the implementation of the above approach:

## C++

 `// C++ program to find the``// count of rotations``#include ``using` `namespace` `std;` `// Function to return the count``// of rotations``int` `countRotation(``int` `arr[], ``int` `n)``{``    ``for``(``int` `i = 1; i < n; i++)``    ``{``        ` `       ``// Find the smallest element``       ``if` `(arr[i] < arr[i - 1])``       ``{``           ``// Return its index``           ``return` `i;``       ``}``    ``}``    ` `    ``// If array is not``    ``// rotated at all``    ``return` `0;``}` `// Driver Code``int` `main()``{``    ``int` `arr1[] = { 4, 5, 1, 2, 3 };``    ``int` `n = ``sizeof``(arr1) / ``sizeof``(``int``);``    ` `    ``cout << countRotation(arr1, n);``}` `// This code is contributed by jrishabh99`

## Java

 `// Java Program to find the``// count of rotations``public` `class` `GFG {` `    ``// Function to return the count of``    ``// rotations``    ``public` `static` `int` `countRotation(``int``[] arr,``                                    ``int` `n)``    ``{``        ``for` `(``int` `i = ``1``; i < n; i++) {``            ``// Find the smallest element``            ``if` `(arr[i] < arr[i - ``1``]) {``                ``// Return its index``                ``return` `i;``            ``}``        ``}``        ``// If array is not``        ``// rotated at all``        ``return` `0``;``    ``}` `    ``// Driver Code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int``[] arr1 = { ``4``, ``5``, ``1``, ``2``, ``3` `};` `        ``System.out.println(``            ``countRotation(``                ``arr1,``                ``arr1.length));``    ``}``}`

## Python3

 `# Python3 program to find the``# count of rotations` `# Function to return the count``# of rotations``def` `countRotation(arr, n):``    ` `    ``for` `i ``in` `range` `(``1``, n):``        ` `        ``# Find the smallest element``        ``if` `(arr[i] < arr[i ``-` `1``]):``            ` `            ``# Return its index``            ``return` `i``    ` `    ``# If array is not``    ``# rotated at all``    ``return` `0` `# Driver Code``if` `__name__ ``=``=` `"__main__"``:``    ` `    ``arr1 ``=` `[ ``4``, ``5``, ``1``, ``2``, ``3` `]``    ``n ``=` `len``(arr1)``    ` `    ``print``(countRotation(arr1, n))` `# This code is contributed by chitranayal`

## C#

 `// C# program to find the count of rotations``using` `System;``class` `GFG{` `// Function to return the count of``// rotations``public` `static` `int` `countRotation(``int``[] arr,``                                ``int` `n)``{``    ``for``(``int` `i = 1; i < n; i++)``    ``{``        ` `    ``// Find the smallest element``    ``if` `(arr[i] < arr[i - 1])``    ``{``            ` `        ``// Return its index``        ``return` `i;``    ``}``    ``}``    ` `    ``// If array is not``    ``// rotated at all``    ``return` `0;``}` `// Driver Code``public` `static` `void` `Main(String[] args)``{``    ``int``[] arr1 = { 4, 5, 1, 2, 3 };` `    ``Console.WriteLine(countRotation(arr1,``                                    ``arr1.Length));``}``}` `// This code is contributed by gauravrajput1`

## Javascript

 ``
Output:
`2`

Time Complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach:
To optimize the above approach, we will use Binary Search. We can notice that, after being sorted and rotated, the given array is divided into two halves with non-decreasing elements, which is the only pre-requisite for binary search. Perform a recursive binary search in the array to find the index of the smallest element.

Below is the implementation of the above approach:

## C++

 `// C++ program to implement the``// above approach``#include ``using` `namespace` `std;` `// Function to return the``// count of rotations``int` `countRotation(``int` `arr[], ``int` `low,``                             ``int` `high)``{``    ` `    ``// If array is not rotated``    ``if` `(low > high)``    ``{``        ``return` `0;``    ``}` `    ``int` `mid = low + (high - low) / 2;` `    ``// Check if current element is``    ``// greater than the next``    ``// element``    ``if` `(mid < high && arr[mid] > arr[mid + 1])``    ``{``        ` `        ``// The next element is``        ``// the smallest``        ``return` `mid + 1;``    ``}` `    ``// Check if current element is``    ``// smaller than it's previous``    ``// element``    ``if` `(mid > low && arr[mid] < arr[mid - 1])``    ``{``        ` `        ``// Current element is``        ``// the smallest``        ``return` `mid;``    ``}` `    ``// Check if current element is``    ``// greater than lower bound``    ``if` `(arr[mid] > arr[low])``    ``{``        ` `        ``// The sequence is increasing``        ``// so far``        ``// Search for smallest``        ``// element on the right``        ``// subarray``        ``return` `countRotation(arr, mid + 1,``                             ``high);``    ``}` `    ``if` `(arr[mid] < arr[high])``    ``{``        ` `        ``// Smallest element lies on the``        ``// left subarray``        ``return` `countRotation(arr, low,``                             ``mid - 1);``    ``}``    ``else``    ``{``        ` `        ``// Search for the smallest``        ``// element on both subarrays``        ``int` `rightIndex = countRotation(arr,``                                       ``mid + 1,``                                       ``high);``        ``int` `leftIndex = countRotation(arr, low,``                                      ``mid - 1);``        ``if` `(rightIndex == 0)``        ``{``            ``return` `leftIndex;``        ``}``        ``return` `rightIndex;``    ``}``}` `// Driver code   ``int` `main()``{``    ``int` `arr1[] = { 4, 5, 1, 2, 3 };``    ``int` `N = ``sizeof``(arr1) / ``sizeof``(arr1[0]);``    ` `    ``cout << countRotation(arr1, 0, N - 1);``    ` `    ``return` `0;``}` `// This code is contributed by divyeshrabadiya07`

## Java

 `// Java Program to implement``// the above approach` `public` `class` `GFG {` `    ``// Function to return the``    ``// count of rotations``    ``public` `static` `int` `countRotation(``int``[] arr,``                                    ``int` `low,``                                    ``int` `high)``    ``{``        ``// If array is not rotated``        ``if` `(low > high) {``            ``return` `0``;``        ``}` `        ``int` `mid = low + (high - low) / ``2``;` `        ``// Check if current element is``        ``// greater than the next``        ``// element` `        ``if` `(mid < high``            ``&& arr[mid] > arr[mid + ``1``]) {``            ``// the next element is``            ``// the smallest``            ``return` `mid + ``1``;``        ``}` `        ``// Check if current element is``        ``// smaller than it's previous``        ``// element``        ``if` `(mid > low``            ``&& arr[mid] < arr[mid - ``1``]) {``            ``// Current element is``            ``// the smallest``            ``return` `mid;``        ``}` `        ``// Check if current element is``        ``// greater than lower bound` `        ``if` `(arr[mid] > arr[low]) {``            ``// The sequence is increasing``            ``// so far``            ``// Search for smallest``            ``// element on the right``            ``// subarray``            ``return` `countRotation(arr,``                                ``mid + ``1``,``                                ``high);``        ``}` `        ``if` `(arr[mid] < arr[high]) {``            ``// Smallest element lies on the``            ``// left subarray``            ``return` `countRotation(arr,``                                ``low,``                                ``mid - ``1``);``        ``}` `        ``else` `{``            ``// Search for the smallest``            ``// element on both subarrays``            ``int` `rightIndex = countRotation(arr,``                                        ``mid + ``1``,``                                        ``high);``            ``int` `leftIndex = countRotation(arr,``                                        ``low,``                                        ``mid - ``1``);` `            ``if` `(rightIndex == ``0``) {``                ``return` `leftIndex;``            ``}` `            ``return` `rightIndex;``        ``}``    ``}` `    ``// Driver Program``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int``[] arr1 = { ``4``, ``5``, ``1``, ``2``, ``3` `};` `        ``System.out.println(``            ``countRotation(``                ``arr1,``                ``0``, arr1.length``                    ``- ``1``));``    ``}``}`

## Python3

 `# Python3 program to implement the``# above approach` `# Function to return the``# count of rotations``def` `countRotation(arr, low, high):` `    ``# If array is not rotated``    ``if` `(low > high):``        ``return` `0` `    ``mid ``=` `low ``+` `(high ``-` `low) ``/``/` `2` `    ``# Check if current element is``    ``# greater than the next``    ``# element``    ``if` `(mid < high ``and` `arr[mid] > arr[mid ``+` `1``]):` `        ``# The next element is``        ``# the smallest``        ``return` `mid ``+` `1` `    ``# Check if current element is``    ``# smaller than it's previous``    ``# element``    ``if` `(mid > low ``and` `arr[mid] < arr[mid ``-` `1``]):` `        ``# Current element is``        ``# the smallest``        ``return` `mid` `    ``# Check if current element is``    ``# greater than lower bound``    ``if` `(arr[mid] > arr[low]):` `        ``# The sequence is increasing``        ``# so far``        ``# Search for smallest``        ``# element on the right``        ``# subarray``        ``return` `countRotation(arr, mid ``+` `1``, high)` `    ``if` `(arr[mid] < arr[high]):` `        ``# Smallest element lies on the``        ``# left subarray``        ``return` `countRotation(arr, low, mid ``-` `1``)` `    ``else``:` `        ``# Search for the smallest``        ``# element on both subarrays``        ``rightIndex ``=` `countRotation(arr,``                                   ``mid ``+` `1``,``                                   ``high)``        ``leftIndex ``=` `countRotation(arr, low,``                                  ``mid ``-` `1``)``        ` `        ``if` `(rightIndex ``=``=` `0``):``            ``return` `leftIndex` `        ``return` `rightIndex` `# Driver code``if` `__name__ ``=``=` `'__main__'``:``    ` `    ``arr1 ``=` `[ ``4``, ``5``, ``1``, ``2``, ``3` `]``    ``N ``=` `len``(arr1)` `    ``print``(countRotation(arr1, ``0``, N ``-` `1``))` `# This code is contributed by mohit kumar 29`

## C#

 `// C# program to implement``// the above approach``using` `System;` `class` `GFG{` `// Function to return the``// count of rotations``public` `static` `int` `countRotation(``int``[] arr,``                                ``int` `low,``                                ``int` `high)``{` `    ``// If array is not rotated``    ``if` `(low > high)``    ``{``        ``return` `0;``    ``}` `    ``int` `mid = low + (high - low) / 2;` `    ``// Check if current element is``    ``// greater than the next``    ``// element``    ``if` `(mid < high &&``        ``arr[mid] > arr[mid + 1])``    ``{``        ` `        ``// The next element is``        ``// the smallest``        ``return` `mid + 1;``    ``}` `    ``// Check if current element is``    ``// smaller than it's previous``    ``// element``    ``if` `(mid > low &&``        ``arr[mid] < arr[mid - 1])``    ``{``        ` `        ``// Current element is``        ``// the smallest``        ``return` `mid;``    ``}` `    ``// Check if current element is``    ``// greater than lower bound``    ``if` `(arr[mid] > arr[low])``    ``{``        ` `        ``// The sequence is increasing``        ``// so far``        ``// Search for smallest``        ``// element on the right``        ``// subarray``        ``return` `countRotation(arr,``                             ``mid + 1,``                             ``high);``    ``}` `    ``if` `(arr[mid] < arr[high])``    ``{``        ` `        ``// Smallest element lies on the``        ``// left subarray``        ``return` `countRotation(arr, low,``                             ``mid - 1);``    ``}``    ` `    ``else``    ``{``        ` `        ``// Search for the smallest``        ``// element on both subarrays``        ``int` `rightIndex = countRotation(arr,``                                       ``mid + 1,``                                       ``high);``        ``int` `leftIndex = countRotation(arr, low,``                                      ``mid - 1);` `        ``if` `(rightIndex == 0)``        ``{``            ``return` `leftIndex;``        ``}``        ``return` `rightIndex;``    ``}``}` `// Driver code``public` `static` `void` `Main(String[] args)``{``    ``int``[] arr1 = { 4, 5, 1, 2, 3 };` `    ``Console.WriteLine(countRotation(arr1, 0,``                            ``arr1.Length - 1));``}``}` `// This code is contributed by 29AjayKumar`

## Javascript

 ``
Output:
`2`

Time Complexity: O(N)
The complexity will be O(logN) for an array without duplicates. But if the array contains duplicates, then it will recursively call the search for both halves. So the worst-case complexity will be O(N).

Auxiliary Space:O(N)
At worst case, the recursion call stack will have N/2 recursion calls at a time.

My Personal Notes arrow_drop_up
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}