← DiffPush

Find how many times array is rotated

Baseline Binary Search · 1D Arrays O(log N) · O(1)

Recovering the Carousel Offset

A circular parts carousel was advanced an unknown number of right steps, and the control software must recover that offset to re-sync its slot numbering. The offset equals how far the smallest part code has travelled from the head of the display. Determine it with logarithmic probes over the wrapped ascending sequence.

Input: An integer N and an array Arr of N distinct integers, originally ascending and then right-rotated K times.

Output: The value of K, the number of right rotations applied.

Constraints

• 1 <= N <= 10^5
• 1 <= Arr[i] <= 10^7
• All values are distinct
• An O(log N) algorithm is required

Examples

Example 1

Input: {"N":5,"Arr":[5,1,2,3,4]}
Output: 1
The ascending order 1,2,3,4,5 was advanced one step, leaving 5 stranded at the head.

Example 2

Input: {"N":5,"Arr":[1,2,3,4,5]}
Output: 0
The carousel was never advanced, so the offset is zero.

Solve this in your browser →

Also on LeetCode ↗