A storage carousel originally held n distinct bin IDs arranged in strictly increasing order. At some point the carousel was rotated by an unknown amount r (0 <= r < n): scanning the current arrangement from the start, you now see the last r original entries followed by the first n - r original entries (a cyclic rotation; r = 0 means no rotation happened).
Given the current (rotated) arrangement of n distinct integers, determine r - equivalently, the 0-indexed position of the smallest value in the arrangement. Print r.
Line 1: an integer n.
Line 2: n space-separated distinct integers, a rotation of some strictly increasing sequence.
A single integer: r, the number of positions the carousel was rotated (0 <= r < n).
Example 1
Input
5 4 5 6 1 2
Expected
3
Explanation
The original sorted order is 1 2 4 5 6. This arrangement shows the last 3 entries (4,5,6) followed by the first 2 (1,2), so it was rotated by r=3; the minimum value 1 sits at index 3.
Example 2
Input
4 1 2 3 4
Expected
0
Explanation
The array is already in sorted order, so r=0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →