educative.io

Educative

Duplicates seem to work with original solution

With this current solution I can’t seem to be finding an edge case were duplicates seem to cause an issue.

Can someone provide an edge case where this solution would not work for a sorted array with duplicates?

def count_rotations(arr):
  start, end = 0, len(arr) - 1

  if arr[start] < arr[end]:
    return 0

  while start < end:
    mid = (start + end) // 2

    # This means mid - 1 element is the largest 
    if mid > start and arr[mid] < arr[mid - 1]:
      return mid
    # This means mid is the largest element
    if mid < end and arr[mid] > arr[mid + 1]:
      return mid + 1
    
    # first part of the array is sorted
    if arr[start] <= arr[mid]:
      start = mid + 1
    else:
      end = mid - 1



def main():
  print(count_rotations([10, 15, 1, 3, 8]))
  print(count_rotations([4, 5, 7, 9, 10, -1, 2]))
  print(count_rotations([1, 3, 8, 10]))
  print(count_rotations([3, 3, 7, 3]))
  print(count_rotations([3, 7, 7, 3]))


main()

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6063579138621440

Hi @Demos. I couldn’t find any edge case for which this solution causes an issue. The only exceptional case I found was that if you give an array with all the same numbers like this: [1,1,1,1], it should return 0, but It is returning None.

I hope this helps.
Happy Learning :smiley: