Given an ascending sorted rotated array Arr of distinct integers of size N. The array is right rotated K times. Find the value of K.
Example 1:
Input:
N = 5
Arr[] = {5, 1, 2, 3, 4}
Output: 1
Explanation: The given array is 5 1 2 3 4. 
The original sorted array is 1 2 3 4 5. 
We can see that the array was rotated 
1 times to the right.
Example 2:
Input:
N = 5
Arr[] = {1, 2, 3, 4, 5}
Output: 0
Explanation: The given array is not rotated.
Your Task:
Complete the function findKRotation() which takes array arr and size n, as input parameters and returns an integer representing the answer. You don't to print answer or take inputs.
Expected Time Complexity: O(log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <=10^{5}
1 <= Arr_{i} <= 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Complete search

Starter code: #User function Template for python3

class Solution:

    def findKRotation(self,arr,  n):

        # code here

Solutions:
class Solution:

	def findKRotation(self, arr, n):
		low = 0
		high = n - 1
		while low <= high:
			if high == low:
				return low
			mid = low + (high - low) // 2
			if arr[mid + 1] < arr[mid] and high > mid:
				return mid + 1
			if arr[mid] < arr[mid - 1] and low < mid:
				return mid
			if arr[high] > arr[mid]:
				high = mid - 1
			else:
				low = mid + 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		for i in range(1, n):
			if arr[i] < arr[i - 1]:
				return i
				break
		return 0


class Solution:

	def findKRotation(self, arr, n):
		el = min(arr)
		if arr.index(el) != 0:
			return arr.index(el)
		else:
			return 0


class Solution:

	def findKRotation(self, arr, n):
		temp = arr[:]
		temp.sort()
		return abs(temp.index(min(temp)) - arr.index(min(arr)))


class Solution:

	def findKRotation(self, arr, n):
		i = 0
		j = arr[-1]
		while arr[i] > j:
			i += 1
		return i


class Solution:

	def findKRotation(self, arr, n):
		if arr[0] < arr[n - 1]:
			return 0
		start = 0
		end = len(arr) - 1
		while start < end:
			mid = start + (end - start) // 2
			if arr[0] <= arr[mid]:
				start = mid + 1
			else:
				end = mid
		return start


class Solution:

	def findKRotation(self, arr, n):
		left = 0
		right = n - 1
		while left <= right:
			mid = left + (right - left) // 2
			if mid < right and arr[mid] > arr[mid + 1]:
				return mid + 1
			if mid > left and arr[mid - 1] > arr[mid]:
				return mid
			if arr[left] <= arr[mid]:
				left = mid + 1
			else:
				right = mid - 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		l = 0
		h = n - 1
		if arr[l] <= arr[h]:
			return l
		while l < h:
			mid = (l + h) // 2
			if arr[mid] > arr[mid + 1]:
				return mid + 1
			elif arr[mid] < arr[mid - 1]:
				return mid
			elif arr[l] <= arr[mid]:
				l = mid + 1
			else:
				h = mid - 1


import numpy as np

class Solution:

	def findKRotation(self, arr, n):
		mini = arr[0]
		rot = 0
		for i in range(n):
			if arr[i] < mini:
				mini = arr[i]
				rot = i
		return rot


import numpy as np

class Solution:

	def findKRotation(self, arr, n):
		arr = np.array(arr) - np.array(sorted(arr))
		count = 0
		for ele in arr:
			if ele > 0:
				count += 1
		return count


class Solution:

	def findKRotation(self, arr, n):
		return arr.index(min(arr))


class Solution:

	def findKRotation(self, arr, n):
		l = 0
		r = len(arr) - 1
		mid = 0
		if n == 1:
			return 0
		if arr[0] < arr[r]:
			return 0
		while l <= r:
			mid = l + (r - l) // 2
			if arr[mid] > arr[mid + 1]:
				return mid + 1
			if arr[mid] < arr[l]:
				r = mid - 1
			if arr[mid] >= arr[l]:
				l = mid + 1
		return l + 1


class Solution:

	def findKRotation(self, arr, n):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			prev = (mid - 1 + n) % n
			next = (mid + 1) % n
			if arr[mid] <= arr[prev] and arr[mid] <= arr[next]:
				return mid
			elif arr[mid] <= arr[high]:
				high = mid - 1
			elif arr[mid] >= arr[low]:
				low = mid + 1
		return 0
		s = 0
		e = len(arr) - 1
		while s <= e:
			mid = s + (e - s) // 2
			nxt = (mid + 1) % n
			prv = (mid + n - 1) % n
			if arr[mid] <= arr[nxt] and arr[mid] <= arr[prv]:
				return mid
			elif arr[mid] >= arr[s]:
				s = mid + 1
			elif arr[mid] <= arr[e]:
				e = mid - 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		(i, j) = (0, n - 1)
		while i <= j:
			m = (i + j) // 2
			if arr[m] < arr[0]:
				j = m - 1
			else:
				i = m + 1
		return i % n


class Solution:

	def findKRotation(self, arr, n):
		nums = arr
		lengthOfNums = len(nums)
		start = 0
		end = lengthOfNums - 1
		pivot = 0
		while start <= end:
			mid = (start + end) // 2
			if mid - 1 >= 0 and nums[mid - 1] > nums[mid]:
				pivot = mid
				break
			elif nums[mid] < nums[start]:
				end = mid - 1
			elif nums[mid] > nums[start]:
				if nums[mid] <= nums[end]:
					end = mid - 1
				elif nums[mid] > nums[end]:
					start = mid + 1
			elif nums[mid] == nums[start]:
				start = mid + 1
		return pivot


class Solution:

	def findKRotation(self, arr, n):
		start = 0
		end = n - 1
		while start <= end:
			mid = start + (end - start) // 2
			nexti = (mid + 1) % n
			prev = (mid + n - 1) % n
			if arr[mid] <= arr[nexti] and arr[mid] <= arr[prev]:
				return mid
			elif arr[mid] <= arr[end]:
				end = mid - 1
			elif arr[start] <= arr[mid]:
				start = mid + 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		n = len(arr)
		left = 0
		right = n - 1
		while left <= right:
			if arr[left] <= arr[right]:
				return left
			mid = (left + right) // 2
			next = (mid + 1) % n
			prev = (mid + n - 1) % n
			if arr[mid] <= arr[next] and arr[mid] <= arr[prev]:
				return mid
			elif arr[mid] <= arr[right]:
				right = mid - 1
			elif arr[mid] >= arr[left]:
				left = mid + 1
		return -1


class Solution:

	def findKRotation(self, arr, n):
		a = []
		for i in arr:
			a.append(i)
		a.sort()
		count = abs(a.index(min(a)) - arr.index(min(arr)))
		return count


class Solution:

	def findKRotation(self, arr, n):
		i = 0
		j = n - 1
		min1 = 1000000
		ind = 0
		while i <= j:
			if arr[i] <= arr[j]:
				if min1 > arr[i]:
					ind = i
					min1 = arr[i]
				break
			mid = (i + j) // 2
			if arr[i] <= arr[mid]:
				if arr[i] < min1:
					ind = i
					min1 = arr[i]
				i = mid + 1
			else:
				if arr[mid] < min1:
					ind = mid
					min1 = arr[mid]
				j = mid - 1
		return ind


class Solution:

	def countRotations(self, arr, low, high):
		if high < low:
			return 0
		if high == low:
			return low
		mid = low + (high - low) // 2
		if mid < high and arr[mid + 1] < arr[mid]:
			return mid + 1
		if mid > low and arr[mid] < arr[mid - 1]:
			return mid
		if arr[high] > arr[mid]:
			return self.countRotations(arr, low, mid - 1)
		return self.countRotations(arr, mid + 1, high)

	def findKRotation(self, arr, n):
		return self.countRotations(arr, 0, n - 1)


class Solution:

	def findKRotation(self, arr, n):
		lo = 0
		hi = n - 1
		if arr[lo] <= arr[hi]:
			return 0
		while lo <= hi:
			mid = (lo + hi) // 2
			if arr[mid] > arr[mid + 1]:
				return mid + 1
			elif arr[mid] < arr[mid - 1]:
				return mid
			elif arr[lo] <= arr[mid]:
				lo = mid + 1
			elif arr[mid] <= arr[hi]:
				hi = mid - 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		c = [i for i in arr]
		c.sort()
		d = c[0]
		return arr.index(d)


class Solution(object):

	def findKRotation(self, nums, n):
		(left, right) = (0, n - 1)
		if n <= 1 or nums[left] < nums[right]:
			return 0
		while left < right:
			mid = (left + right) // 2
			(prev, curr, next) = (nums[mid - 1], nums[mid], nums[mid + 1])
			if curr > next:
				return mid + 1
			if prev > curr:
				return mid
			if nums[0] < curr:
				left = mid + 1
			else:
				right = mid - 1


from typing import List

class Solution:

	def findKRotation(self, arr: List[int], n: int) -> int:
		(a, b) = (0, n - 1)
		while a <= b:
			mid = (a + b) // 2
			prev = (mid + n - 1) % n
			next_idx = (mid + 1) % n
			if arr[mid] <= arr[prev] and arr[mid] <= arr[next_idx]:
				return mid
			if arr[mid] <= arr[b]:
				b = mid - 1
			else:
				a = mid + 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		l = 0
		r = n - 1
		index = 0
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] >= arr[0]:
				l = mid + 1
			else:
				r = mid - 1
		return l % n


class Solution:

	def findKRotation(self, arr, n):
		x = min(arr)
		l = arr[:]
		l.sort()
		return abs(l.index(x) - arr.index(x))


class Solution:

	def findKRotation(self, arr, n):
		m = min(arr)
		c = 0
		for i in range(n):
			if arr[i] != m:
				c = c + 1
			else:
				break
		return c


class Solution:

	def findKRotation(self, arr, n):
		a = min(arr)
		c = 0
		for i in range(len(arr)):
			if arr[i] == a:
				c = i
			else:
				continue
		return c


class Solution:

	def findKRotation(self, A, n):
		(low, high) = (0, n)
		while low < high:
			mid = (low + high) // 2
			if A[0] <= A[mid]:
				low = mid + 1
			else:
				high = mid
		if low == n:
			return 0
		return low


class Solution:

	def findKRotation(self, arr, n):
		l = 0
		r = n - 1
		while l <= r:
			mid = (l + r) // 2
			if arr[l] >= arr[mid] and arr[mid] >= arr[r]:
				return r
			if mid == 0 or arr[mid - 1] > arr[mid]:
				return mid
			if arr[mid] < arr[l]:
				r = mid - 1
			elif arr[mid] > arr[r]:
				l = mid + 1
			else:
				return l
		return -1


class Solution:

	def findKRotation(self, arr, n):
		if arr[0] < arr[-1] or n == 1:
			return 0
		for i in range(n - 1):
			if arr[i] > arr[i - 1] and arr[i] > arr[i + 1]:
				return i + 1
		return n


class Solution:

	def findKRotation(self, arr, n):
		low = 0
		high = n - 1
		while low <= high:
			mid = low + (high - low) // 2
			prev = (mid - 1 + n) % n
			next = (mid + 1) % n
			if arr[mid] <= arr[prev] and arr[mid] <= arr[next]:
				return mid
			elif arr[mid] <= arr[high]:
				high = mid - 1
			elif arr[mid] >= arr[low]:
				low = mid + 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		ans = 0
		for i in range(n - 1):
			if arr[i] > arr[i + 1]:
				ans = i + 1
			else:
				continue
		return ans


class Solution:

	def rot_bs(self, arr, start, end, n):
		while start <= end:
			mid = start + (end - start) // 2
			prev_ele = (mid - 1 + n) % n
			next_ele = (mid + 1) % n
			if arr[mid] < arr[prev_ele] and arr[mid] < arr[next_ele]:
				return mid
			elif arr[mid] <= arr[end]:
				end = mid - 1
			elif arr[start] <= arr[mid]:
				start = mid + 1

	def findKRotation(self, arr, n):
		if arr[0] <= arr[n - 1]:
			return 0
		return self.rot_bs(arr, 0, n - 1, n)


class Solution:

	def findKRotation(self, nums, n):
		low = 0
		high = n - 1
		while low < high:
			mid = low + high >> 1
			if nums[mid] > nums[high]:
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def findKRotation(self, arr, n):
		lo = 0
		hi = len(arr) - 1
		if len(arr) == 1 or arr[lo] < arr[hi]:
			return 0
		while lo <= hi:
			mid = (lo + hi) // 2
			if arr[mid] < arr[mid - 1]:
				return mid
			if arr[mid] > arr[mid + 1]:
				return mid + 1
			if arr[lo] < arr[mid]:
				lo = mid + 1
			else:
				hi = mid - 1


import sys

class Solution:

	def findKRotation(self, arr, n):
		(l, r) = (0, len(arr) - 1)
		minNum = arr[0]
		index = 0
		while l <= r:
			if arr[l] <= arr[r]:
				if minNum > arr[l]:
					index = l
					break
			mid = (l + r) // 2
			if minNum > arr[mid]:
				minNum = arr[mid]
				index = mid
			if arr[mid] >= arr[l]:
				l = mid + 1
			else:
				r = mid - 1
		return index


class Solution:

	def findKRotation(self, arr, n):
		(l, h) = (0, n - 1)
		MAX = float('-inf')
		if arr[l] <= arr[h]:
			return 0
		while l <= h:
			mid = (l + h) // 2
			if arr[mid] > MAX:
				MAX = arr[mid]
				max_index = mid
			if arr[mid] < arr[l]:
				h = mid - 1
			else:
				l = mid + 1
		return max_index + 1


class Solution:

	def findKRotation(self, nums, n):
		left = 0
		right = len(nums) - 1
		ans = 0
		while left <= right:
			mid = (left + right) // 2
			if nums[mid] < nums[mid - 1]:
				ans = mid
				break
			if nums[mid] < nums[0]:
				right = mid - 1
			else:
				left = mid + 1
		return ans


class Solution:

	def findKRotation(self, nums, n):
		s = 0
		e = n - 1
		pivot = -1
		while s <= e:
			mid = s + (e - s) // 2
			if mid < e and nums[mid] > nums[mid + 1]:
				pivot = mid
				break
			elif mid > s and nums[mid - 1] > nums[mid]:
				pivot = mid - 1
				break
			if nums[mid] <= nums[s]:
				e = mid - 1
			elif nums[s] < nums[mid]:
				s = mid + 1
		if pivot == -1:
			return 0
		return pivot + 1


class Solution:

	def findKRotation(self, arr, n):
		x = min(arr)
		for i in range(n):
			if arr[i] == x:
				return i
				break


class Solution:

	def findKRotation(self, nums, n):
		start = 0
		end = len(nums) - 1
		while start <= end:
			mid = (start + end) // 2
			if mid < end and nums[mid] > nums[mid + 1]:
				return mid + 1
			if mid < end and nums[mid] < nums[mid - 1]:
				return mid
			if nums[start] == nums[mid] == nums[end] and start != mid != end:
				if nums[start] > nums[start + 1]:
					return start + 1
				start += 1
				if nums[end - 1] > nums[end]:
					return end
				end -= 1
			elif nums[mid] > nums[start] or (nums[mid] == nums[start] and nums[mid] > nums[end]):
				start = mid + 1
			else:
				end = mid - 1
		return 0


class Solution:

	def findKRotation(self, arr, n):
		l = 0
		h = n - 1
		while l < h:
			m = (l + h) // 2
			if arr[m] <= arr[h]:
				h = m
			else:
				l = m
			if arr[m] > arr[m + 1]:
				return m + 1
		return l


class Solution:

	def findKRotation(self, arr, n):
		cnt = 1
		for i in range(1, n):
			if arr[i - 1] < arr[i]:
				cnt += 1
			else:
				break
		return cnt % n


class Solution:

	def findKRotation(self, arr, n):
		m = float('inf')
		idx = 0
		for i in range(n):
			if m > arr[i]:
				m = arr[i]
				idx = i
		return idx


class Solution:

	def findKRotation(self, nums, n):
		rotation_pivot = 0
		(l, r, mid) = (0, n - 1, 0)
		if n == 1:
			return 0
		while l <= r:
			mid = (l + r) // 2
			if mid < n - 1:
				if nums[mid] > nums[mid + 1]:
					return mid + 1
			if mid > 0:
				if nums[mid] < nums[mid - 1]:
					return mid
			if nums[l] > nums[mid]:
				r = mid - 1
			else:
				l = mid + 1
		return 0


def b_search(arr, start, end):
	middle = (start + end) // 2
	if start == end:
		return start
	while start < end:
		if arr[middle] < arr[middle - 1] and arr[middle] < arr[middle + 1]:
			return middle
		elif arr[middle] < arr[end]:
			return b_search(arr, start, middle - 1)
		else:
			return b_search(arr, middle + 1, end)
	return -1

class Solution:

	def findKRotation(self, arr, n):
		result = b_search(arr, 0, n - 1)
		if result == -1:
			return 0
		else:
			return result


class Solution:

	def findKRotation(self, arr, n):
		l = []
		l.extend(arr)
		l.sort()
		return arr.index(l[0])