Dada una array arr[] de N elementos distintos, la tarea es verificar si es posible hacer que la array aumente o disminuya rotando la array en cualquier dirección.
Ejemplos:
Entrada: arr[] = {4, 5, 6, 2, 3}
Salida: Sí La
array se puede rotar como {2, 3, 4, 5, 6}
Entrada: arr[] = {1, 2, 4, 3 , 5}
Salida: No
Enfoque: Hay cuatro posibilidades:
- Si la array ya está aumentando , la respuesta es Sí .
- Si la array ya está disminuyendo , la respuesta es Sí .
- Si la array se puede hacer creciente, esto puede ser posible si la array dada primero aumenta hasta el elemento máximo y luego disminuye.
- Si la array se puede hacer decreciente, esto puede ser posible si la array dada primero disminuye hasta el elemento mínimo y luego aumenta.
Si no es posible hacer que la array aumente o disminuya, imprima No.
A continuación se muestra la implementación del enfoque anterior:
Javascript
<script>
// javascript implementation of the approach
// Function that returns true if the array
// can be made increasing or decreasing
// after rotating it in any direction
function isPossible(a , n) {
// If size of the array is less than 3
if (n <= 2)
return true;
var flag = 0;
// Check if the array is already decreasing
for (i = 0; i < n - 2; i++) {
if (!(a[i] > a[i + 1] && a[i + 1] > a[i + 2])) {
flag = 1;
break;
}
}
// If the array is already decreasing
if (flag == 0)
return true;
flag = 0;
// Check if the array is already increasing
for (i = 0; i < n - 2; i++) {
if (!(a[i] < a[i + 1] && a[i + 1] < a[i + 2])) {
flag = 1;
break;
}
}
// If the array is already increasing
if (flag == 0)
return true;
// Find the indices of the minimum
// && the maximum value
var val1 = Number.MAX_VALUE, mini = -1, val2 = Number.MIN_VALUE, maxi = 0;
for (i = 0; i < n; i++) {
if (a[i] < val1) {
mini = i;
val1 = a[i];
}
if (a[i] > val2) {
maxi = i;
val2 = a[i];
}
}
flag = 1;
// Check if we can make array increasing
for (i = 0; i < maxi; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;
}
}
// If the array is increasing upto max index
// && minimum element is right to maximum
if (flag == 1 && maxi + 1 == mini) {
flag = 1;
// Check if array increasing again or not
for (i = mini; i < n - 1; i++) {
if (a[i] > a[i + 1]) {
flag = 0;
break;
}
}
if (flag == 1)
return true;
}
flag = 1;
// Check if we can make array decreasing
for (i = 0; i < mini; i++) {
if (a[i] < a[i + 1]) {
flag = 0;
break;
}
}
// If the array is decreasing upto min index
// && minimum element is left to maximum
if (flag == 1 && maxi - 1 == mini) {
flag = 1;
// Check if array decreasing again or not
for (i = maxi; i < n - 1; i++) {
if (a[i] < a[i + 1]) {
flag = 0;
break;
}
}
if (flag == 1)
return true;
}
// If it is not possible to make the
// array increasing or decreasing
return false;
}
// Driver code
var a = [ 4, 5, 6, 2, 3 ];
var n = a.length;
if (isPossible(a, n))
document.write("Yes");
else
document.write("No");
// This code contributed by umadevi9616
</script>
Yes
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
¡ Consulte el artículo completo sobre Comprobar si es posible hacer que la array aumente o disminuya girando la array para obtener más detalles!
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