Home/

...

/

Problem Challenge 3

Problem Challenge 3

Problem statement

Given an array of numbers that is sorted in ascending order and is rotated k times around a pivot, find k. You can assume that the array does not have any duplicates.

Dry-run templates

The following is the implementation of the solution provided for the problem posed in the Problem Challenge 3 lesson.

Press + to interact
Python 3.8
def count_rotations(arr):
  start, end = 0, len(arr) - 1
  while start < end:
    mid = start + (end - start) // 2
    # if mid is greater than the next element
    if mid < end and arr[mid] > arr[mid + 1]:
      return mid + 1
    # if mid is smaller than the previous element
    if mid > start and arr[mid - 1] > arr[mid]:
      return mid
    if arr[start] < arr[mid]:  # left side is sorted, so the pivot is on right side
      start = mid + 1
    else:  # right side is sorted, so the pivot is on the left side
      end = mid - 1
  return 0  # the array has not been rotated
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]))
main()

Sample input #1

Input: [10, 15, 1, 3, 8]

Line number

Loop iteration

start

end

mid

Return value

2

-

0

4

-

-

3-17

1

0

4

2

mid = 2

Sample input #2

Students may be encouraged to fill the dry-run table with the following input:

Input: [4, 5, 7, 9, 10, -1, 2]

Line number

Loop iteration

start

end

mid

Return value

2

-

0

6

-

-

3-17

1

4

6

3

-

...

...

...

...

...

...

Trace generation

We’ll iterate over our input array and maintain start, end and mid indices. There are five conditions that need to be checked:

  • If the element at mid is greater than the next element, the array has undergone mid+1 rotations.
  • If the element at mid is smaller than the previous element, the array has undergone mid rotations.
  • If the element at start index is less than the element at the mid index, the left side of the array is sorted and the pivot is on the right side.
  • If the element at start index is greater than the element at the mid index, the right side of the array is sorted and the pivot is on the left side.
  • If end and start cross, that is, end becomes less than start, the array is sorted and there are 0 rotations.
Press + to interact
Python 3.8
def count_rotations(arr):
  print("Given array: ", arr, sep = "")
  print("")
  start, end = 0, len(arr) - 1
  print("start: ", start, ", end: ",end, sep = "")
  print("")
  i = 1
  while start < end:
    print("\tLoop iteration: ", i, sep = "")
    i+=1
    print("\t\tstart: ", start, ", end: ",end, sep = "")
    mid = start + (end - start) // 2
    print("\t\tmid: start + (end - start) // 2 = ", mid, sep = "")
    # if mid is greater than the next element
    if mid < end and arr[mid] > arr[mid + 1]:
      print("\t\tmid element is greater than the next element: ", arr[mid], " > ", arr[mid+1], " --> return mid + 1: ", mid + 1, sep = "")
      return mid + 1
    # if mid is smaller than the previous element
    if mid > start and arr[mid - 1] > arr[mid]:
      print("\t\tmid element is smaller than the previous element: ", arr[mid], " < ", arr[mid-1], " --> return mid: ", mid, sep = "")
      return mid
    if arr[start] < arr[mid]:  # left side is sorted, so the pivot is on right side
      print("\t\tarr[start] < arr[mid]: ", arr[start], " < ", arr[mid], " --> update start", sep = "")
      start = mid + 1
      print("\t\t\tstart: mid + 1 --> ", mid, " + 1 = ",start )
    else:  # right side is sorted, so the pivot is on the left side
      print("\t\tarr[start] > arr[mid]: ", arr[start], " >= ", arr[mid], " --> update end", sep = "")
      end = mid - 1
      print("\t\t\tend: mid - 1 --> ", mid, " - 1 = ",end )
    print("")
  print("Since end < start: ", end, " < ", start, ", the array is sorted, and we return 0 rotations.", sep = "")
  return 0  # the array has not been rotated
def main():
  inputarrays = [[10, 15, 1, 3, 8], [4, 5, 7, 9, 10, -1, 2],[1, 3, 8, 10]]
  for i in inputarrays:
    rotations = count_rotations(i)
    print("")
    if rotations == 0:
      print("The array has not been rotated.")
    else:
      print("The array has been rotated ", rotations," times.", sep = "")
    print(("-"*100)+"\n")
main()