Find out how many times the array is rotated
M2P FintechThe problem
Given an integer array nums of size n, sorted in ascending order with distinct values. The array has been right rotated an unknown number of times, between 0 and n-1 (including). Determine the number of rotations performed on the array.
Input : nums = [4, 5, 6, 7, 0, 1, 2, 3] Output: 4 Explanation: The original array should be [0, 1, 2, 3, 4, 5, 6, 7]. So, we can notice that the array has been rotated 4 times.
Input: nums = [3, 4, 5, 1, 2] Output: 3 Explanation: The original array should be [1, 2, 3, 4, 5]. So, we can notice that the array has been rotated 3 times.
Input: nums = [4, 5, 1, 2]
- n == nums.length
- 1 <= n <= 104
- -104 <= nums[i] <= 104
- All the integers of nums are unique.
cpp
class Solution {
public:
int findKRotation(vector<int> &nums) {
}
};java
class Solution {
public int findKRotation(ArrayList<Integer> nums) {
}
}python
class Solution:
def findKRotation(self, nums):javascript
class Solution {
findKRotation(nums) {
}
}csharp
public class Solution
{
public int findKRotation(int[] nums)
{
// Your code goes here
}
}go
func findKRotation(nums []int) int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Recognize that right rotations equal the minimum index.
- 02Binary-search for the minimum.
- 03Return zero for an already sorted interval.
- 04Use middle versus high to discard the sorted half.
- 05Return the converged index.
Reference answer
Then expect these follow-ups
How would duplicates affect the search?
Tests: follow-up reasoning
How can you search for a target once you know this pivot?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question