Add algorithm for how many times an array has been rotated in O(log N) (TheAlgorithms#2448)

nirmalya8 · web-flow · commit a352a4905e39 · 2021-10-04T08:51:10.000+03:00
diff --git a/Searches/howManyTimesRotated.java b/Searches/howManyTimesRotated.java
@@ -0,0 +1,66 @@
+/*
+    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 mimimum 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
+*/
+
+import java.util.*;
+
+class howManyTimesRotated
+{
+    public static void main(String[] args) 
+    {
+        Scanner sc = new Scanner(System.in);
+        int n = sc.nextInt();
+        int[] a = new int[n];
+        for(int i = 0; i < n; i++)
+            a[i] = sc.nextInt();
+
+        System.out.println("The array has been rotated "+rotated(a)+" times");
+        sc.close();
+
+    }
+
+    public static int rotated(int[] a)
+    {
+        int low = 0;
+        int high = a.length-1;
+        int mid=0; // low + (high-low)/2 = (low + high)/2
+        int i=0;
+        while(low<=high)
+        {
+            mid = low + (high-low)/2;
+            i++;
+            if(a[mid]<a[mid-1] && a[mid]<a[mid+1])
+            {
+                break;
+            }
+            else if(a[mid]>a[mid-1] && a[mid]<a[mid+1])
+            {
+                high = mid+1;
+            }
+            else if(a[mid]>a[mid-1] && a[mid]>a[mid+1])
+            {
+                low = mid-1;
+            }
+        }
+        
+        return mid;
+    }
+}
