Dada una array de N enteros distintos. La tarea es escribir un programa para verificar si esta array está ordenada y girada en sentido contrario a las agujas del reloj. Una array ordenada no se considera ordenada y rotada, es decir, debe haber al menos una rotación.
Ejemplos :
Input : arr[] = { 3, 4, 5, 1, 2 }
Output : YES
The above array is sorted and rotated.
Sorted array: {1, 2, 3, 4, 5}.
Rotating this sorted array clockwise
by 3 positions, we get: { 3, 4, 5, 1, 2}
Input: arr[] = {7, 9, 11, 12, 5}
Output: YES
Input: arr[] = {1, 2, 3}
Output: NO
Input: arr[] = {3, 4, 6, 1, 2, 5}
Output: NO
Enfoque :
- Encuentre el elemento mínimo en la array.
- Ahora, si se ordena la array y luego se giran todos los elementos antes del elemento mínimo estarán en orden creciente y todos los elementos después del elemento mínimo también estarán en orden creciente.
- Compruebe si todos los elementos antes del elemento mínimo están en orden creciente.
- Compruebe si todos los elementos después del elemento mínimo están en orden creciente.
- Compruebe si el último elemento de la array es más pequeño que el elemento inicial.
- Si se cumplen las tres condiciones anteriores, imprima SÍ ; de lo contrario, imprima NO .
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to check if an array is
// sorted and rotated clockwise
#include <climits>
#include <iostream>
using namespace std;
// Function to check if an array is
// sorted and rotated clockwise
void checkIfSortRotated(int arr[], int n)
{
int minEle = INT_MAX;
int maxEle = INT_MIN;
int minIndex = -1;
// Find the minimum element
// and it's index
for (int i = 0; i < n; i++) {
if (arr[i] < minEle) {
minEle = arr[i];
minIndex = i;
}
}
int flag1 = 1;
// Check if all elements before minIndex
// are in increasing order
for (int i = 1; i < minIndex; i++) {
if (arr[i] < arr[i - 1]) {
flag1 = 0;
break;
}
}
int flag2 = 1;
// Check if all elements after minIndex
// are in increasing order
for (int i = minIndex + 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
flag2 = 0;
break;
}
}
// Check if last element of the array
// is smaller than the element just
// starting element of the array
// for arrays like [3,4,6,1,2,5] - not circular array
if (flag1 && flag2 && (arr[n - 1] < arr[0]))
cout << "YES";
else
cout << "NO";
}
// Driver code
int main()
{
int arr[] = { 3, 4, 5, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
checkIfSortRotated(arr, n);
return 0;
}
Java
// Java program to check if an
// array is sorted and rotated
// clockwise
import java.io.*;
class GFG {
// Function to check if an array is
// sorted and rotated clockwise
static void checkIfSortRotated(int arr[], int n)
{
int minEle = Integer.MAX_VALUE;
int maxEle = Integer.MIN_VALUE;
int minIndex = -1;
// Find the minimum element
// and it's index
for (int i = 0; i < n; i++) {
if (arr[i] < minEle) {
minEle = arr[i];
minIndex = i;
}
}
boolean flag1 = true;
// Check if all elements before
// minIndex are in increasing order
for (int i = 1; i < minIndex; i++) {
if (arr[i] < arr[i - 1]) {
flag1 = false;
break;
}
}
boolean flag2 = true;
// Check if all elements after
// minIndex are in increasing order
for (int i = minIndex + 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
flag2 = false;
break;
}
}
// check if the minIndex is 0, i.e the first element
// is the smallest , which is the case when array is
// sorted but not rotated.
if (minIndex == 0) {
System.out.print("NO");
return;
}
// Check if last element of the array
// is smaller than the element just
// before the element at minIndex
// starting element of the array
// for arrays like [3,4,6,1,2,5] - not sorted
// circular array
if (flag1 && flag2 && (arr[n - 1] < arr[0]))
System.out.println("YES");
else
System.out.print("NO");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 4, 5, 1, 2 };
int n = arr.length;
// Function Call
checkIfSortRotated(arr, n);
}
}
// This code is contributed
// by inder_verma.
Python3
# Python3 program to check if an
# array is sorted and rotated clockwise
import sys
# Function to check if an array is
# sorted and rotated clockwise
def checkIfSortRotated(arr, n):
minEle = sys.maxsize
maxEle = -sys.maxsize - 1
minIndex = -1
# Find the minimum element
# and it's index
for i in range(n):
if arr[i] < minEle:
minEle = arr[i]
minIndex = i
flag1 = 1
# Check if all elements before
# minIndex are in increasing order
for i in range(1, minIndex):
if arr[i] < arr[i - 1]:
flag1 = 0
break
flag2 = 2
# Check if all elements after
# minIndex are in increasing order
for i in range(minIndex + 1, n):
if arr[i] < arr[i - 1]:
flag2 = 0
break
# Check if last element of the array
# is smaller than the element just
# before the element at minIndex
# starting element of the array
# for arrays like [3,4,6,1,2,5] - not sorted circular array
if (flag1 and flag2 and
arr[n - 1] < arr[0]):
print("YES")
else:
print("NO")
# Driver code
arr = [3, 4, 5, 1, 2]
n = len(arr)
# Function Call
checkIfSortRotated(arr, n)
# This code is contributed
# by Shrikant13
C#
// C# program to check if an
// array is sorted and rotated
// clockwise
using System;
class GFG {
// Function to check if an array is
// sorted and rotated clockwise
static void checkIfSortRotated(int[] arr, int n)
{
int minEle = int.MaxValue;
// int maxEle = int.MinValue;
int minIndex = -1;
// Find the minimum element
// and it's index
for (int i = 0; i < n; i++) {
if (arr[i] < minEle) {
minEle = arr[i];
minIndex = i;
}
}
bool flag1 = true;
// Check if all elements before
// minIndex are in increasing order
for (int i = 1; i < minIndex; i++) {
if (arr[i] < arr[i - 1]) {
flag1 = false;
break;
}
}
bool flag2 = true;
// Check if all elements after
// minIndex are in increasing order
for (int i = minIndex + 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
flag2 = false;
break;
}
}
// Check if last element of the array
// is smaller than the element just
// before the element at minIndex
// starting element of the array
// for arrays like [3,4,6,1,2,5] - not circular
// array
if (flag1 && flag2 && (arr[n - 1] < arr[0]))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
// Driver code
public static void Main()
{
int[] arr = { 3, 4, 5, 1, 2 };
int n = arr.Length;
// Function Call
checkIfSortRotated(arr, n);
}
}
// This code is contributed
// by inder_verma.
PHP
<?php
// PHP program to check if an
// array is sorted and rotated
// clockwise
// Function to check if an array
// is sorted and rotated clockwise
function checkIfSortRotated($arr, $n)
{
$minEle = PHP_INT_MAX;
$maxEle = PHP_INT_MIN;
$minIndex = -1;
// Find the minimum element
// and it's index
for ($i = 0; $i <$n; $i++)
{
if ($arr[$i] < $minEle)
{
$minEle = $arr[$i];
$minIndex = $i;
}
}
$flag1 = 1;
// Check if all elements before
// minIndex are in increasing order
for ( $i = 1; $i <$minIndex; $i++)
{
if ($arr[$i] < $arr[$i - 1])
{
$flag1 = 0;
break;
}
}
$flag2 = 1;
// Check if all elements after
// minIndex are in increasing order
for ($i = $minIndex + 1; $i <$n; $i++)
{
if ($arr[$i] < $arr[$i - 1])
{
$flag2 = 0;
break;
}
}
// Check if last element of the array
// is smaller than the element just
// starting element of the array
// for arrays like [3,4,6,1,2,5] - not sorted circular array
if ($flag1 && $flag2 &&
($arr[$n - 1] < $arr[$0]))
echo( "YES");
else
echo( "NO");
}
// Driver code
$arr = array(3, 4, 5, 1, 2);
//Function Call
$n = count($arr);
checkIfSortRotated($arr, $n);
// This code is contributed
// by inder_verma.
?>
Javascript
<script>
// Javascript program to check if an
// array is sorted and rotated
// clockwise
// Function to check if an array is
// sorted and rotated clockwise
function checkIfSortRotated(arr, n)
{
let minEle = Number.MAX_VALUE;
// int maxEle = int.MinValue;
let minIndex = -1;
// Find the minimum element
// and it's index
for (let i = 0; i < n; i++) {
if (arr[i] < minEle) {
minEle = arr[i];
minIndex = i;
}
}
let flag1 = true;
// Check if all elements before
// minIndex are in increasing order
for (let i = 1; i < minIndex; i++) {
if (arr[i] < arr[i - 1]) {
flag1 = false;
break;
}
}
let flag2 = true;
// Check if all elements after
// minIndex are in increasing order
for (let i = minIndex + 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
flag2 = false;
break;
}
}
// Check if last element of the array
// is smaller than the element just
// before the element at minIndex
// starting element of the array
// for arrays like [3,4,6,1,2,5] - not circular
// array
if (flag1 && flag2 && (arr[n - 1] < arr[0]))
document.write("YES");
else
document.write("NO");
}
let arr = [ 3, 4, 5, 1, 2 ];
let n = arr.length;
// Function Call
checkIfSortRotated(arr, n);
// This code is contributed by mukesh07.
</script>
Producción
YES
Método 2:
Acercarse:
- Tome dos variables, digamos x e y, inicializadas como 0.
- Ahora atraviesa la array.
- Si encontramos que el elemento anterior es más pequeño que el actual, aumentamos x en uno.
- De lo contrario, si encontramos que el elemento anterior es mayor que el actual, aumentamos y en uno.
- Después del recorrido, si alguno de xey no es igual a 1, devuelve falso.
- Si cualquiera de x o y es 1, entonces compare el último elemento con el primer elemento (el elemento 0 como el actual y el último elemento como el anterior). Es decir, si el último elemento es mayor, aumente y en uno; de lo contrario, aumente x en uno.
- Nuevamente verifique x e y, si alguno es igual a uno, devuelva verdadero. es decir, la array está ordenada y girada. De lo contrario, devuelve falso.
Explicación:
- La idea es sencilla. Si la array se ordena y rota, los elementos aumentan o disminuyen, pero con una excepción. Entonces contamos cuántas veces el elemento es mayor que su elemento anterior, y cuántas veces el elemento es más pequeño que su elemento anterior.
- El caso especial es cuando la array está ordenada pero no rotada. para esto verifique el último elemento con el primer elemento especialmente.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
bool checkRotatedAndSorted(int arr[], int n)
{
// Your code here
// Initializing two variables x,y as zero.
int x = 0, y = 0;
// Traversing array 0 to last element.
// n-1 is taken as we used i+1.
for (int i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1])
x++;
else
y++;
}
// If till now both x,y are greater than 1 means
// array is not sorted. If both any of x,y is zero
// means array is not rotated.
if (x == 1 || y == 1) {
// Checking for last element with first.
if (arr[n - 1] < arr[0])
x++;
else
y++;
// Checking for final result.
if (x == 1 || y == 1)
return true;
}
// If still not true then definitely false.
return false;
}
// Driver Code Starts.
int main()
{
int arr[] = { 4, 5, 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
if (checkRotatedAndSorted(arr, n))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
Java
import java.io.*;
class GFG {
// Function to check if an array is
// Sorted and rotated clockwise
static boolean checkIfSortRotated(int arr[], int n)
{
// Initializing two variables x,y as zero.
int x = 0, y = 0;
// Traversing array 0 to last element.
// n-1 is taken as we used i+1.
for (int i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1])
x++;
else
y++;
}
// If till now both x,y are greater
// than 1 means array is not sorted.
// If both any of x,y is zero means
// array is not rotated.
if (x == 1 || y == 1) {
// Checking for last element with first.
if (arr[n - 1] < arr[0])
x++;
else
y++;
// Checking for final result.
if (x == 1 || y == 1)
return true;
}
// If still not true then definitely false.
return false;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 1, 2, 3, 4 };
int n = arr.length;
// Function Call
boolean x = checkIfSortRotated(arr, n);
if (x == true)
System.out.println("YES");
else
System.out.println("NO");
}
}
Python3
def checkRotatedAndSorted(arr, n):
# Your code here
# Initializing two variables x,y as zero.
x = 0
y = 0
# Traversing array 0 to last element.
# n-1 is taken as we used i+1.
for i in range (n-1):
if (arr[i] < arr[i + 1]):
x += 1
else:
y += 1
# If till now both x,y are greater than 1 means
# array is not sorted. If both any of x,y is zero
# means array is not rotated.
if (x == 1 or y == 1):
# Checking for last element with first.
if (arr[n - 1] < arr[0]):
x += 1
else:
y += 1
# Checking for final result.
if (x == 1 or y == 1):
return True
# If still not true then definitely false.
return False
# Driver Code Starts.
arr = [ 4, 5, 1, 2, 3 ]
n = len(arr)
# Function Call
if (checkRotatedAndSorted(arr, n)):
print("YES")
else:
print("NO")
# This code is contributed by shivanisinghss2110
C#
using System;
public class GFG {
// Function to check if an array is
// Sorted and rotated clockwise
static bool checkIfSortRotated(int []arr, int n)
{
// Initializing two variables x,y as zero.
int x = 0, y = 0;
// Traversing array 0 to last element.
// n-1 is taken as we used i+1.
for (int i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1])
x++;
else
y++;
}
// If till now both x,y are greater
// than 1 means array is not sorted.
// If both any of x,y is zero means
// array is not rotated.
if (x == 1 || y == 1) {
// Checking for last element with first.
if (arr[n - 1] < arr[0])
x++;
else
y++;
// Checking for readonly result.
if (x == 1 || y == 1)
return true;
}
// If still not true then definitely false.
return false;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 5, 1, 2, 3, 4 };
int n = arr.Length;
// Function Call
bool x = checkIfSortRotated(arr, n);
if (x == true)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JavaScript Function to check if an array is
// Sorted and rotated clockwise
function checkIfSortRotated(arr, n)
{
// Initializing two variables x,y as zero.
var x = 0, y = 0;
// Traversing array 0 to last element.
// n-1 is taken as we used i+1.
for (var i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1])
x++;
else
y++;
}
// If till now both x,y are greater
// than 1 means array is not sorted.
// If both any of x,y is zero means
// array is not rotated.
if (x == 1 || y == 1) {
// Checking for last element with first.
if (arr[n - 1] < arr[0])
x++;
else
y++;
// Checking for final result.
if (x == 1 || y == 1)
return true;
}
// If still not true then definitely false.
return false;
}
// Driver code
var arr = [ 5, 1, 2, 3, 4 ];
var n = arr.length;
// Function Call
var x = checkIfSortRotated(arr, n);
if (x == true)
document.write("YES");
else
document.write("NO");
// This code is contributed by shivanisinghss2110
</script>
Producción
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(1)