Dada una array arr[] de tamaño N que tiene distintos números ordenados en orden creciente y la array se ha rotado a la derecha (es decir, el último elemento se desplazará cíclicamente a la posición inicial de la array) k número de veces, la tarea es encontrar el valor de k .
Ejemplos:
C++
// C++ program to find number of rotations
// in a sorted and rotated array.
#include <bits/stdc++.h>
using namespace std;
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
int countRotations(int arr[], int n)
{
// We basically find index of minimum
// element
int min = arr[0], min_index = 0;
for (int i = 0; i < n; i++) {
if (min > arr[i]) {
min = arr[i];
min_index = i;
}
}
return min_index;
}
// Driver code
int main()
{
int arr[] = { 15, 18, 2, 3, 6, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countRotations(arr, n);
return 0;
}
// This code is contributed by Adutya Kumar(adityakumar129)
C
// C program to find number of rotations
// in a sorted and rotated array.
#include <stdio.h>
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
int countRotations(int arr[], int n)
{
// We basically find index of minimum
// element
int min = arr[0], min_index = 0;
for (int i = 0; i < n; i++) {
if (min > arr[i]) {
min = arr[i];
min_index = i;
}
}
return min_index;
}
// Driver code
int main()
{
int arr[] = { 15, 18, 2, 3, 6, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("%d", countRotations(arr, n));
return 0;
}
// This code is contributed by Adutya Kumar(adityakumar129)
Java
// Java program to find number of
// rotations in a sorted and rotated
// array.
import java.io.*;
import java.lang.*;
import java.util.*;
class LinearSearch {
// Returns count of rotations for an
// array which is first sorted in
// ascending order, then rotated
static int countRotations(int arr[], int n)
{
// We basically find index of minimum
// element
int min = arr[0], min_index = 0;
for (int i = 0; i < n; i++) {
if (min > arr[i]) {
min = arr[i];
min_index = i;
}
}
return min_index;
}
// Driver program to test above functions
public static void main(String[] args)
{
int arr[] = { 15, 18, 2, 3, 6, 12 };
int n = arr.length;
System.out.println(countRotations(arr, n));
}
}
// This code is contributed by Adutya Kumar(adityakumar129)
Python3
# Python3 program to find number # of rotations in a sorted and # rotated array. # Returns count of rotations for # an array which is first sorted # in ascending order, then rotated def countRotations(arr, n): # We basically find index # of minimum element min = arr[0] min_index = 0 for i in range(0, n): if (min > arr[i]): min = arr[i] min_index = i return min_index; # Driver code arr = [15, 18, 2, 3, 6, 12] n = len(arr) print(countRotations(arr, n)) # This code is contributed by Smitha Dinesh Semwal
C#
// c# program to find number of
// rotations in a sorted and rotated
// array.
using System;
class LinearSearch
{
// Returns count of rotations for an
// array which is first sorted in
// ascending order, then rotated
static int countRotations(int []arr, int n)
{
// We basically find index of minimum
// element
int min = arr[0], min_index = 0;
for (int i = 0; i < n; i++)
{
if (min > arr[i])
{
min = arr[i];
min_index = i;
}
}
return min_index;
}
// Driver program to test above functions
public static void Main ()
{
int []arr = {15, 18, 2, 3, 6, 12};
int n = arr.Length;
Console.WriteLine(countRotations(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find number
// of rotations in a sorted
// and rotated array.
// Returns count of rotations
// for an array which is first
// sorted in ascending order,
// then rotated
function countRotations($arr, $n)
{
// We basically find index
// of minimum element
$min = $arr[0];
$min_index = 0;
for ($i = 0; $i < $n; $i++)
{
if ($min > $arr[$i])
{
$min = $arr[$i];
$min_index = $i;
}
}
return $min_index;
}
// Driver code
$arr = array(15, 18, 2,
3, 6, 12);
$n = sizeof($arr);
echo countRotations($arr, $n);
// This code is contributed
// by ajit
?>
Javascript
<script>
// Javascript program to find number of rotations
// in a sorted and rotated array.
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
function countRotations(arr, n)
{
// We basically find index of minimum
// element
let min = arr[0], min_index = 0
for (let i = 0; i < n; i++)
{
if (min > arr[i])
{
min = arr[i];
min_index = i;
}
}
return min_index;
}
// Driver Code
let arr = [15, 18, 2, 3, 6, 12];
let n = arr.length;
document.write(countRotations(arr, n));
</script>
C++
// Binary Search based C++ program to find number
// of rotations in a sorted and rotated array.
#include <bits/stdc++.h>
using namespace std;
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
int countRotations(int arr[], int low, int high)
{
// This condition is needed to handle the case
// when the array is not rotated at all
if (high < low)
return 0;
// If there is only one element left
if (high == low)
return low;
// Find mid
int mid = low + (high - low) / 2; /*(low + high)/2;*/
// Check if element (mid+1) is minimum element.
// Consider the cases like {3, 4, 5, 1, 2}
if (mid < high && arr[mid + 1] < arr[mid])
return (mid + 1);
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return mid;
// Decide whether we need to go to left half or
// right half
if (arr[high] > arr[mid])
return countRotations(arr, low, mid - 1);
return countRotations(arr, mid + 1, high);
}
// Driver code
int main()
{
int arr[] = { 15, 18, 2, 3, 6, 12 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << countRotations(arr, 0, N - 1);
return 0;
}
Java
// Java program to find number of
// rotations in a sorted and rotated
// array.
import java.io.*;
import java.lang.*;
import java.util.*;
class BinarySearch {
// Returns count of rotations for an array
// which is first sorted in ascending order,
// then rotated
static int countRotations(int arr[], int low, int high)
{
// This condition is needed to handle
// the case when array is not rotated
// at all
if (high < low)
return 0;
// If there is only one element left
if (high == low)
return low;
// Find mid
// /*(low + high)/2;*/
int mid = low + (high - low) / 2;
// Check if element (mid+1) is minimum
// element. Consider the cases like
// {3, 4, 5, 1, 2}
if (mid < high && arr[mid + 1] < arr[mid])
return (mid + 1);
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return mid;
// Decide whether we need to go to left
// half or right half
if (arr[high] > arr[mid])
return countRotations(arr, low, mid - 1);
return countRotations(arr, mid + 1, high);
}
// Driver program to test above functions
public static void main(String[] args)
{
int arr[] = { 15, 18, 2, 3, 6, 12 };
int N = arr.length;
System.out.println(countRotations(arr, 0, N - 1));
}
}
// This code is contributed by Chhavi
Python3
# Binary Search based Python3 # program to find number of # rotations in a sorted and # rotated array. # Returns count of rotations for # an array which is first sorted # in ascending order, then rotated def countRotations(arr, n): start = 0 end = n-1 # Finding the index of minimum of the array # index of min would be equal to number to rotation while start<=end: mid = start+(end-start)//2 # Calculating the previous(prev) # and next(nex) index of mid prev = (mid-1+n)%n nex = (mid+1)%n # Checking if mid is minimum if arr[mid]<arr[prev]\ and arr[mid]<=arr[nex]: return mid # if not selecting the unsorted part of array elif arr[mid]<arr[start]: end = mid-1 elif arr[mid]>arr[end]: start = mid+1 else: return 0 # Driver code if __name__ == '__main__': arr = [15, 18, 2, 3, 6, 12] N = len(arr) print(countRotations(arr, N)) # This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find number of
// rotations in a sorted and rotated
// array.
using System;
class BinarySearch {
// Returns count of rotations for an array
// which is first sorted in ascending order,
// then rotated
static int countRotations(int[] arr, int low, int high)
{
// This condition is needed to handle
// the case when array is not rotated
// at all
if (high < low)
return 0;
// If there is only one element left
if (high == low)
return low;
// Find mid
// /*(low + high)/2;*/
int mid = low + (high - low) / 2;
// Check if element (mid+1) is minimum
// element. Consider the cases like
// {3, 4, 5, 1, 2}
if (mid < high && arr[mid + 1] < arr[mid])
return (mid + 1);
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return mid;
// Decide whether we need to go to left
// half or right half
if (arr[high] > arr[mid])
return countRotations(arr, low, mid - 1);
return countRotations(arr, mid + 1, high);
}
// Driver program to test above functions
public static void Main()
{
int[] arr = { 15, 18, 2, 3, 6, 12 };
int N = arr.Length;
Console.WriteLine(countRotations(arr, 0, N - 1));
}
}
// This code is contributed by vt_m.
PHP
<?php
// Binary Search based PHP
// program to find number
// of rotations in a sorted
// and rotated array.
// Returns count of rotations
// for an array which is
// first sorted in ascending
// order, then rotated
function countRotations($arr,
$low, $high)
{
// This condition is needed
// to handle the case when
// array is not rotated at all
if ($high < $low)
return 0;
// If there is only
// one element left
if ($high == $low)
return $low;
// Find mid
$mid = $low + ($high -
$low) / 2;
// Check if element (mid+1)
// is minimum element. Consider
// the cases like {3, 4, 5, 1, 2}
if ($mid < $high &&
$arr[$mid + 1] < $arr[$mid])
return (int)($mid + 1);
// Check if mid itself
// is minimum element
if ($mid > $low &&
$arr[$mid] < $arr[$mid - 1])
return (int)($mid);
// Decide whether we need
// to go to left half or
// right half
if ($arr[$high] > $arr[$mid])
return countRotations($arr, $low,
$mid - 1);
return countRotations($arr,
$mid + 1,
$high);
}
// Driver code
$arr = array(15, 18, 2, 3, 6, 12);
$N = sizeof($arr);
echo countRotations($arr, 0, $N - 1);
// This code is contributed bu ajit
?>
Javascript
<script>
// Binary Search based C++ program to find number
// of rotations in a sorted and rotated array.
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
function countRotations(arr, low, high)
{
// This condition is needed to handle the case
// when the array is not rotated at all
if (high < low)
return 0;
// If there is only one element left
if (high == low)
return low;
// Find mid
let mid = Math.floor(low + (high - low)/2); /*(low + high)/2;*/
// Check if element (mid+1) is minimum element.
// Consider the cases like {3, 4, 5, 1, 2}
if (mid < high && arr[mid+1] < arr[mid])
return (mid+1);
// Check if mid itself is minimum element
if (mid > low && arr[mid] < arr[mid - 1])
return mid;
// Decide whether we need to go to left half or
// right half
if (arr[high] > arr[mid])
return countRotations(arr, low, mid-1);
return countRotations(arr, mid+1, high);
}
// Driver code
let arr = [15, 18, 2, 3, 6, 12];
let N = arr.length;
document.write(countRotations(arr, 0, N-1));
// This code is contributed by Surbhi Tyagi.
</script>
C++
#include <bits/stdc++.h>
using namespace std;
// Returns count of rotations
// for an array which is first sorted
// in ascending order, then rotated
// Observation: We have to return
// index of the smallest element
int countRotations(int arr[], int n)
{
int low = 0, high = n - 1;
while (low <= high) {
// if first element is mid or
// last element is mid
// then simply use modulo so it
// never goes out of bound.
int mid = low + (high - low) / 2;
int prev = (mid - 1 + n) % n;
int next = (mid + 1) % n;
if (arr[mid] <= arr[prev] && arr[mid] <= arr[next])
return mid;
else if (arr[mid] <= arr[high])
high = mid - 1;
else if (arr[mid] >= arr[low])
low = mid + 1;
}
return 0;
}
// Driver code
int main()
{
int arr[] = { 15, 18, 2, 3, 6, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countRotations(arr, n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Returns count of rotations
// for an array which is first sorted
// in ascending order, then rotated
// Observation: We have to return
// index of the smallest element
static int countRotations(int[] arr, int n)
{
int low = 0, high = n - 1;
while (low <= high) {
// if first element is mid or
// last element is mid
// then simply use modulo so it
// never goes out of bound.
int mid = low + (high - low) / 2;
int prev = (mid - 1 + n) % n;
int next = (mid + 1) % n;
if (arr[mid] <= arr[prev]
&& arr[mid] <= arr[next])
return mid;
else if (arr[mid] <= arr[high])
high = mid - 1;
else if (arr[mid] >= arr[low])
low = mid + 1;
}
return 0;
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 15, 18, 2, 3, 6, 12 };
int n = arr.length;
System.out.println(countRotations(arr, n));
}
}
// This code is contributed by shinjanpatra
Python3
# Returns count of rotations for an array which # is first sorted in ascending order, then rotated # Observation: We have to return index of the smallest element def countRotations(arr, n): low = 0 high = n - 1 while(low <= high): # if first element is mid or # last element is mid # then simply use modulo # so it never goes out of bound. mid = low + ((high - low) // 2) prev = (mid - 1 + n) % n next = (mid + 1) % n if(arr[mid] <= arr[prev] and arr[mid] <= arr[next]): return mid elif (arr[mid] <= arr[high]): high = mid - 1 elif (arr[mid] >= arr[low]): low = mid + 1 return 0 # Driver code arr = [15, 18, 2, 3, 6, 12] n = len(arr) print(countRotations(arr, n)) # This code is contributed by shinjanpatra.
C#
// C# program for the above approach
using System;
class GFG {
// Returns count of rotations
// for an array which is first sorted
// in ascending order, then rotated
// Observation: We have to return
// index of the smallest element
static int countRotations(int[] arr, int n)
{
int low = 0, high = n - 1;
while (low <= high) {
// if first element is mid or
// last element is mid
// then simply use modulo so it
// never goes out of bound.
int mid = low + (high - low) / 2;
int prev = (mid - 1 + n) % n;
int next = (mid + 1) % n;
if (arr[mid] <= arr[prev]
&& arr[mid] <= arr[next])
return mid;
else if (arr[mid] <= arr[high])
high = mid - 1;
else if (arr[mid] >= arr[low])
low = mid + 1;
}
return 0;
}
// Driver Code
public static void Main()
{
int[] arr = { 15, 18, 2, 3, 6, 12 };
int n = arr.Length;
Console.Write(countRotations(arr, n));
}
}
// This code is contributed by saurabh_jaiswal.
Javascript
<script>
// Returns count of rotations for an array which
// is first sorted in ascending order, then rotated
//Observation: We have to return index of the smallest element
function countRotations(arr, n)
{
let low =0 , high = n-1;
while(low<=high){
let mid = low + Math.floor((high-low)/2) ;
let prev = (mid-1 + n) %n , next = (mid+1)%n;//if first element is mid or
//last element is mid then simply use modulo so it never goes out of bound.
if(arr[mid]<=arr[prev] && arr[mid]<=arr[next])
return mid;
else if (arr[mid]<=arr[high])
high = mid-1 ;
else if (arr[mid]>=arr[low])
low=mid+1;
}
return 0;
}
// Driver code
let arr = [15, 18, 2, 3, 6, 12];
let n = arr.length;
document.write(countRotations(arr, n));
// This code is contributed by shinjanpatra.
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA