n distinct integers sorted in ascending order. It was cyclically shifted to the right between 1 and n times; one shift moves the last element to the front. For example, [2, 5, 8, 11] turns into [8, 11, 2, 5] after two shifts, and back into [2, 5, 8, 11] after four.
You are given the resulting list ring. Return its smallest element.
Your algorithm should run in O(log n) time.ring=[40, 55, 70, 3, 18] → 3
The original list was [3, 18, 40, 55, 70]; it was shifted 3 places to the right, which moved the smallest value 3 to position 3.
ring=[-6, -2, 8, 13] → -6
The list was shifted by exactly its own length and came back unchanged, so the minimum is first.
ring=[21, -9] → -9
The original list [-9, 21] was shifted once, moving 21 to the front. The minimum is -9.
n = ring.length ≤ 5000ring[i] ≤ 5000ring are distinctring is an ascending list cyclically shifted between 1 and n timesring=[40, 55, 70, 3, 18]
3
Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.