HowManyTimesRotated.java

packagecom.thealgorithms.searches;

importjava.util.Scanner;

/*
 Problem Statement:
 Given an array, find out how many times it has to been rotated
 from its initial sorted position.
 Input-Output:
 Eg. [11,12,15,18,2,5,6,8]
 It has been rotated: 4 times
 (One rotation means putting the first element to the end)
 Note: The array cannot contain duplicates

 Logic:
 The position of the minimum element will give the number of times the array has been rotated
 from its initial sorted position.
 Eg. For [2,5,6,8,11,12,15,18], 1 rotation gives [5,6,8,11,12,15,18,2], 2 rotations
 [6,8,11,12,15,18,2,5] and so on. Finding the minimum element will take O(N) time but, we can use
 Binary Search to find the minimum element, we can reduce the complexity to O(log N). If we look
 at the rotated array, to identify the minimum element (say a[i]), we observe that
 a[i-1]>a[i]<a[i+1].

 Some other test cases:
 1. [1,2,3,4] Number of rotations: 0 or 4(Both valid)
 2. [15,17,2,3,5] Number of rotations: 3
 */
finalclassHowManyTimesRotated {
privateHowManyTimesRotated() {
 }

publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);
intn = sc.nextInt();
int[] a = newint[n];
for (inti = 0; i < n; i++) {
a[i] = sc.nextInt();
 }

System.out.println("The array has been rotated " + rotated(a) + " times");
sc.close();
 }

publicstaticintrotated(int[] a) {
intlow = 0;
inthigh = a.length - 1;
intmid = 0; // low + (high-low)/2 = (low + high)/2

while (low <= high) {
mid = low + (high - low) / 2;

if (a[mid] < a[mid - 1] && a[mid] < a[mid + 1]) {
break;
 } elseif (a[mid] > a[mid - 1] && a[mid] < a[mid + 1]) {
high = mid + 1;
 } elseif (a[mid] > a[mid - 1] && a[mid] > a[mid + 1]) {
low = mid - 1;
 }
 }

returnmid;
 }
}