Posted on by Kalkicode
Code Array

# Find the rotation count in rotated sorted array

Finding the rotation count in a rotated sorted array is a common problem in programming. In a rotated sorted array, an array that was originally sorted is rotated cyclically by an unknown number of positions. The task is to determine how many positions the array has been rotated.

## Problem Statement

Given a rotated sorted array of distinct integers, find the number of positions the array has been rotated. The rotation count corresponds to the index of the smallest element in the rotated array.

## Example

Consider the following rotated sorted array:

``arr = [12, 14, 18, -4, 1, 4, 6, 8, 9, 12]``

The smallest element is `-4` at index `3`. The array has been rotated by 3 positions. Thus, the output should be: "Rotation: 3."

## Idea to Solve

To solve this problem, we can perform a binary search to find the index of the smallest element in the rotated array. The index of the smallest element will correspond to the number of positions the array has been rotated.

## Pseudocode

``````function rotation_count(arr, size):
low = 0
high = size - 1

while low < high:
mid = (low + high) / 2

if arr[mid] > arr[high]:
low = mid + 1
else:
high = mid

return low

// Example usage
arr = [12, 14, 18, -4, 1, 4, 6, 8, 9, 12]
size = size(arr)
rotation = rotation_count(arr, size)
print("Rotation:", rotation)``````

## Algorithm Explanation

1. The `rotation_count` function takes the array and its size as parameters.
2. Initialize two pointers `low` and `high` to the first and last indices of the array.
3. Perform a binary search by calculating the middle index `mid`.
4. Compare the value at index `mid` with the value at index `high`:
• If `arr[mid]` is greater than `arr[high]`, it means the smallest element is in the right half of the array. So, update `low` to `mid + 1`.
• If not, the smallest element is in the left half of the array or at the `mid` index itself. Update `high` to `mid`.
5. Repeat the binary search until `low` is less than `high`.
6. The final value of `low` will be the rotation count.

## Code Solution

``````//C Program
//Find the rotation count in rotated sorted array
#include <stdio.h>

//Rotation count in sorted rotated array
void rotation(int arr[],int size)
{
if(size<=1)
{
return;
}

int i = 0;
//Find First largest element
while(i < size-1 && arr[i] <= arr[i+1])
{
i++;
}

if(i+1 < size)
{
//When rotation count is less than size of array elements
printf("Rotation : %d\n",i+1 );
}
else
{
printf("Rotation : %d\n",0 );
}

}
//Display array elements
void dispay(int arr[],int size)
{

for (int i = 0; i < size; ++i)
{
printf("%3d",arr[i] );
}
printf("\n");
}
int main()
{
//Define the value of array elements
int arr[] ={12,14,18,-4,1,4,6,8,9,12};

//Get the size of array
int size=(sizeof(arr)/sizeof(arr[0]));

dispay(arr,size);
rotation(arr,size);

return 0;
}```
```

#### Output

`````` 12 14 18 -4  1  4  6  8  9 12
Rotation : 3``````
``````/*
C++ Program
Find the Rotation Count in Rotated Sorted array
*/
#include<iostream>

using namespace std;

class MyArray {
public:

//Rotation count in sorted rotated array
void rotation(int arr[], int size) {
if (size <= 1) {
return;
}
int i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i++;
}
if (i + 1 < size) {
//When rotation count is less than size of array elements

cout << "Rotation : " << (i + 1) << "\n";
} else {
cout << "Rotation : 0";
}
}
//Display array elements
void dispay(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MyArray obj = MyArray();
int arr[] = {
12,
14,
18,
-4,
1,
4,
6,
8,
9,
12
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.rotation(arr, size);
return 0;
}```
```

#### Output

``Rotation : 3``
``````/*
Java Program
Find the Rotation Count in Rotated Sorted array
*/

public class MyArray
{
//Rotation count in sorted rotated array
public void rotation(int []arr,int size)
{
if(size<=1)
{
return;
}

int i = 0;
//Find First largest element
while(i < size-1 && arr[i] <= arr[i+1])
{
i++;
}

if(i+1 < size)
{
//When rotation count is less than size of array elements
System.out.print("Rotation :  "+(i+1) +"\n");
}
else
{
System.out.print("Rotation :  0" );
}

}
//Display array elements
public void dispay(int []arr,int size)
{

for (int i = 0; i < size; ++i)
{
System.out.print("  "+arr[i] );
}
System.out.print("\n");
}

public static void main(String[] args) {
MyArray obj = new MyArray();
//Define the value of array elements
int []arr = {12,14,18,-4,1,4,6,8,9,12};
//Get the size of array
int size = arr.length;

obj.rotation(arr,size);
}
}```
```

#### Output

``Rotation : 3``
``````/*
C# Program
Find the Rotation Count in Rotated Sorted array
*/
using System;

public class MyArray {
//Rotation count in sorted rotated array
public void rotation(int[] arr, int size) {
if (size <= 1) {
return;
}
int i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i++;
}
if (i + 1 < size) {
Console.Write("Rotation : " + (i + 1) + "\n");
} else {
Console.Write("Rotation : 0");
}
}
//Display array elements
public void dispay(int[] arr, int size) {
for (int i = 0; i < size; ++i) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[]
//Define the value of array elements
arr = {
12,
14,
18,
-4,
1,
4,
6,
8,
9,
12
};
//Get the size of array
int size = arr.Length;
obj.rotation(arr, size);
}
}```
```

#### Output

``Rotation : 3``
``````<?php
/*
Php Program
Find the Rotation Count in Rotated Sorted array
*/
class MyArray {
//Rotation count in sorted rotated array

public 	function rotation(\$arr, \$size) {
if (\$size <= 1) {
return;
}
\$i = 0;
//Find First largest element
while (\$i < \$size - 1 && \$arr[\$i] <= \$arr[\$i + 1]) {
\$i++;
}
if (\$i + 1 < \$size) {
//When rotation count is less than size of array elements

echo("Rotation : ". (\$i + 1) ."\n");
} else {
echo("Rotation : 0");
}
}
//Display array elements

public 	function dispay(\$arr, \$size) {
for (\$i = 0; \$i < \$size; ++\$i) {
echo(" ". \$arr[\$i]);
}
echo("\n");
}
}

function main() {
\$obj = new MyArray();
//Define the value of array elements
\$arr = array(12, 14, 18, -4, 1, 4, 6, 8, 9, 12);
//Get the size of array
\$size = count(\$arr);
\$obj->rotation(\$arr, \$size);

}
main();```
```

#### Output

``Rotation : 3``
``````/*
Node Js Program
Find the Rotation Count in Rotated Sorted array
*/
class MyArray {
//Rotation count in sorted rotated array
rotation(arr, size) {
if (size <= 1) {
return;
}
var i = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i++;
}

if (i + 1 < size) {
//When rotation count is less than size of array elements

process.stdout.write("Rotation : " + (i + 1) + "\n");
} else {
process.stdout.write("Rotation : 0");
}
}

//Display array elements
dispay(arr, size) {
for (var i = 0; i < size; ++i) {
process.stdout.write(" " + arr[i]);
}

process.stdout.write("\n");
}
}

function main(args) {
var obj = new MyArray();
//Define the value of array elements
var arr = [12, 14, 18, -4, 1, 4, 6, 8, 9, 12];
//Get the size of array
var size = arr.length;
obj.rotation(arr, size);
}

main();```
```

#### Output

``Rotation : 3``
``````# Python 3 Program
# Find the Rotation Count in Rotated Sorted array
class MyArray :
# Rotation count in sorted rotated array
def rotation(self, arr, size) :
if (size <= 1) :
return

i = 0
# Find First largest element
while (i < size - 1 and arr[i] <= arr[i + 1]) :
i += 1

if (i + 1 < size) :
print("Rotation : ", (i + 1) ,"\n", end = "")
else :
print("Rotation : 0", end = "")

# Display array elements
def dispay(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

def main() :
obj = MyArray()
arr = [12, 14, 18, -4, 1, 4, 6, 8, 9, 12]
size = len(arr)
obj.rotation(arr, size)

if __name__ == "__main__":
main()```
```

#### Output

``Rotation :  3``
``````# Ruby Program
# Find the Rotation Count in Rotated Sorted array
class MyArray
# Rotation count in sorted rotated array
def rotation(arr, size)
if (size <= 1)
return
end
i = 0
# Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1])
i += 1
end
if (i + 1 < size)
print("Rotation  :", (i + 1) ,"\n")
else
print("Rotation  :0")
end
end
# Display array elements
def dispay(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyArray.new()
arr = [12, 14, 18, -4, 1, 4, 6, 8, 9, 12]
size = arr.length
obj.rotation(arr, size)
end
main()```
```

#### Output

``````Rotation  :3
``````
``````/*
Scala Program
Find the Rotation Count in Rotated Sorted array
*/
class MyArray {
//Rotation count in sorted rotated array
def rotation(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
}
var i: Int = 0;

//Find First largest element
while (i < size - 1 && arr(i) <= arr(i + 1)) {
i += 1;
}
if (i + 1 < size) {
print("Rotation : " + (i + 1) + "\n");
} else {
print("Rotation : 0");
}
}
//Display array elements
def dispay(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(12, 14, 18, -4, 1, 4, 6, 8, 9, 12);
val size: Int = arr.length;
obj.rotation(arr, size);
}
}```
```

#### Output

``Rotation : 3``
``````/*
Swift Program
Find the Rotation Count in Rotated Sorted array
*/
class MyArray {
//Rotation count in sorted rotated array
func rotation(_ arr: [Int], _ size: Int) {
if (size <= 1) {
return;
}
var i: Int = 0;
//Find First largest element
while (i < size - 1 && arr[i] <= arr[i + 1]) {
i += 1;
}
if (i + 1 < size) {
print("Rotation : ", (i + 1) ,"\n", terminator: "");
} else {
print("Rotation : 0", terminator: "");
}
}
//Display array elements
func dispay(_ arr: [Int], _ size: Int) {
var i: Int = 0;
while (i < size) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [12, 14, 18, -4, 1, 4, 6, 8, 9, 12];
let size: Int = arr.count;
obj.rotation(arr, size);
}
main();```
```

#### Output

``Rotation :  3``

## Time Complexity

The binary search runs in `O(log n)` time, where `n` is the size of the array. Thus, the time complexity of the algorithm is `O(log n)`.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post