Interview Question
Country: United States
Assuming a non-trivial array (not all the same number), and assuming by "clockwise" you mean rotated right... you could walk the array until you find the first inflection point (arr[n] > arr[n+1]) which puts this in O(n) territory. Because duplicates are involved I'm not sure you can do much better than that, though a binary search for the inflection also comes to mind.
See also question id=18325674 here, which seems quite similar.
Your example suggests duplicates are allowed.
- S O U N D W A V E October 20, 2013So jaingok, what would the answer be if I hand you this array:
{1,1,1,1,1,..., 1,1,1,1,1,1,1}
?