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.

New Comment