Python Program to Find the Rotation Count in Rotated Sorted List

by

In the previous article, we have discussed Python Program to Sort a List in Wave Form
Consider a List of distinct numbers that are sorted in ascending order. The list has been rotated k times (clockwise). The task is to determine the value of k.

In simple terms, print the minimum index value to get the rotation count.

Examples:

Example1:

Input:

Given List = [7, 9, 11, 12, 5, 6, 1, 8]

Output:

The number of rotations of a gvn_lst [7, 9, 11, 12, 5, 6, 1, 8] = 6

Example2:

Input:

Given List = [6, 3, 1, 4, 7]

Output:

The number of rotations of a gvn_lst [6, 3, 1, 4, 7] = 1

Program to Find the Rotation Count in Rotated Sorted List in Python

Below are the ways to find the rotation count in the rotated sorted list:

Method #1: Using For Loop (Static Input)

Approach:

  • Give the list as static input and store it in a variable.
  • Calculate the length of the given list using the len() function and store it in another variable.
  • Take a variable say “minim_index” and initialize it with the first element of the given list.
  • Loop from 0 to the length of the given list using the for loop.
  • Check if the value of the variable “minim_index” is greater than the given list of iterator value.
  • If the statement is true then assign the given list of iterator value to the “minim_index”.
  • Store the iterator value in a variable “minim_index”.
  • Print “minim_index” to get the number of rotations of a given list.
  • The Exit of the Program.

Below is the implementation:

# Give the list as static input and store it in a variable.
gvn_lst = [1, 3, 5, 7, 9]
# Calculate the length of the given list using the len() function and
# store it in another variable.
len_lst = len(gvn_lst)
# Take a variable say "minim_index" and initialize it with the first element of
# the given list.
minim_index = gvn_lst[0]
# Loop from 0 to the length of the given list using the for loop.
for itr in range(0, len_lst):
 # Check if the value of the variable "minim_index" is greater than the given list of
 # iterator value.
    if (minim_index > gvn_lst[itr]):
        # If the statement is true then assign the given list of iterator value to the "minim_index".
        minim_index = gvn_lst[itr]
# Store the iterator value in a variable "minim_index".
        minim_index = itr
# Print "minim_index" to get the number of rotations of a given list.
print("The number of rotations of a gvn_lst", gvn_lst, "=", minim_index)

Output:

The number of rotations of a gvn_lst [1, 3, 5, 7, 9] = 1

Method #2: Using For loop (User Input)

Approach:

  • Give the list as user input using list(),map(),input(),and split() functions.
  • Store it in a variable.
  • Calculate the length of the given list using the len() function and store it in another variable.
  • Take a variable say “minim_index” and initialize it with the first element of the given list.
  • Loop from 0 to the length of the given list using the for loop.
  • Check if the value of the variable “minim_index” is greater than the given list of iterator value.
  • If the statement is true then assign the given list of iterator value to the “minim_index”.
  • Store the iterator value in a variable “minim_index”.
  • Print “minim_index” to get the number of rotations of a given list.
  • The Exit of the Program.

Below is the implementation:

# Give the list as user input using list(),map(),input(),and split() functions.
#Store it in a variable.
gvn_lst = list(map(int, input(
   'Enter some random List Elements separated by spaces = ').split()))
# Calculate the length of the given list using the len() function and
# store it in another variable.
len_lst = len(gvn_lst)
# Take a variable say "minim_index" and initialize it with the first element of
# the given list.
minim_index = gvn_lst[0]
# Loop from 0 to the length of the given list using the for loop.
for itr in range(0, len_lst):
 # Check if the value of the variable "minim_index" is greater than the given list of
 # iterator value.
    if (minim_index > gvn_lst[itr]):
        # If the statement is true then assign the given list of iterator value to the "minim_index".
        minim_index = gvn_lst[itr]
# Store the iterator value in a variable "minim_index".
        minim_index = itr
# Print "minim_index" to get the number of rotations of a given list.
print("The number of rotations of a gvn_lst", gvn_lst, "=", minim_index)

Output:

Enter some random List Elements separated by spaces = 6 3 1 4 7
The number of rotations of a gvn_lst [6, 3, 1, 4, 7] = 1

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.