## Introduction

Let's discuss how to calculate the Rotation Count of a rotated sorted array consisting of **distinct** elements, i.e., no of times a sorted array is rotated.

Must Read, __Array Implementation of Queue____ __and __Rabin Karp Algorithm__

## Problem Statement

We are given an array of distinct integers, sorted in increasing order. The array has been rotated (clockwise) k times; find k or the ‘Rotation Count’.

**Intuitive Idea:** If we follow through with some examples, one typical pattern that we would observe is that the no of times array is rotated or Rotation Count = index of the minimum element in the array.

Eg: array = [4,5,1,2]

This array was sorted initially i.e of the form [1,2,4,5]

Let’s rotate the array clockwise one by one element to find the Rotation Count.

Rotation Count 1: shifting 1 back => [5,1,2,4]

Rotation Count 2: shifting 2 back => [4,5,1,2]

Now, after 2 rotation counts, our array looks like the given rotated array.

Also, note here the minimum element is 1, and its index = 2 (considering 0 based indexing).

Try following this for various other examples, and we would observe

**Rotation Count = index of the minimum element in the array**

There are two main approaches to find the index of the minimum element of the array . The first one being prevalent and intuitive i.e., via LINEAR SEARCH.

Let’s quickly discuss this first, and then we’ll cover an approach with better time complexity.