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