Number of rotations (2) P55375


Statement
 

pdf   zip   main.cc   main.py

html

Given a (non empty) circularly sorted vector of integers, find the number of times the vector is rotated. Assume that there are no duplicates in the vector and the rotation is in anti-clockwise direction.

For instance, [8, 9, 10, 2, 5, 6] is rotated three times, [9, 10, 2, 5, 6, 8] is rotated two times, [4, 0, 1, 2, 3] is rotated one time, and [2, 5, 8, 9, 12] is rotated zero times.

Solve this problem with recursion in logarithmic time, using this header in C++:

int number_of_rotations (const vector<int>& v);

or this header in Python:

number_of_rotations(v: list[int]) -> int

Write the specification of the recursive function that you will need to write in a comment at the beginning of such function.

Observation You only need to submit the required procedure; your main program will be ignored.

Information
Author
Jordi Petit
Language
English
Translator
Jordi Petit
Original language
Catalan
Other languages
Catalan
Official solutions
C++ Python
User solutions
C++ Python