Nombre de rotacions (1) P63069

Donat un vector (no buit) circularment ordenat d’enters, es vol trobar el nombre de cops que s’ha rotat. Assumiu que no hi ha duplicats al vector i que la rotació és en sentit antihorari.

Per exemple, [8, 9, 10, 2, 5, 6] s’ha rotat tres cops, [9, 10, 2, 5, 6, 8] s’ha rotat dos cops, [4, 0, 1, 2, 3] s’ha rotat un cop, i [2, 5, 8, 9, 12] s’ha rotat zero cops.

Resoleu aquest problema iterativament en temps logarítmic, usant aquesta capçalera per C++:

O aquesta per Python:

Doneu l’invariant del bucle en un comentari a l’inici del bucle de la funció.

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.