Dada una array arr[ ] con longitud uniforme N , la tarea es encontrar el número de cambios cíclicos (rotaciones) posibles para esta array, de modo que la primera mitad de la array no contenga el elemento máximo.
Ejemplos:
Entrada: N = 6, arr[ ] = { 3, 3, 5, 3, 3, 3 }
Salida: 3
Explicación: El elemento máximo aquí es 5 en el índice 2. Este 5 se puede desplazar a la segunda mitad de la array usando cualquiera de los siguientes tres desplazamientos a la derecha válidos:
- cambiar de 1: (3, 3, 3, 5, 3, 3)
- cambiar por 2: (3, 3, 3, 3, 5, 3)
- cambiar por 3: (3, 3, 3, 3, 3, 5)
Entrada: N = 6, arr[ ] = {8, 8, 9, 8, 8, 9}
Salida: 0
Explicación: cualquier rotación en el artículo no ayudará a eliminar el elemento máximo de la primera mitad, ya que hay dos ocurrencias de 9 en el índice 2 y 5. Entonces, cualquier rotación mantendrá al menos un 9 en el índice 0, 1 o 2.
Enfoque ingenuo: el enfoque más básico para resolver este problema se basa en la siguiente idea:
Encuentre todas las rotaciones de una array dada. Al final, simplemente devuelva el recuento de dichas rotaciones que no tienen el elemento máximo en la primera mitad.
Complejidad de tiempo: O(N 3 ) donde N^2 es para rotaciones y N es para encontrar el máximo en cada rotación.
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea para resolver el problema es atravesar la array y algunos conceptos básicos de matemáticas.
La idea es encontrar la distancia entre los elementos máximos y simplemente verificar si el rango es mayor que la mitad del tamaño de la array. En caso afirmativo, la rotación es posible, o la rotación no es posible.
Para el caso en que la rotación sea posible, podemos encontrar el [rango – (n/2)] como el número válido de rotaciones.
Siga los pasos para resolver el problema:
- En primer lugar, encuentre el elemento máximo
- Luego encuentre los rangos máximos entre pares de elementos máximos.
- Un rango con longitud m agrega max(m-frac(N/2)+1, 0) a la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach.
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of cyclic shifts
int find(int arr[], int N)
{
int maxele = *max_element(arr, arr + N);
int left = -1;
int right = -1;
// Placing left pointer
// On its correct position
for (int i = 0; i < N; i++) {
if (arr[i] == maxele) {
left = i;
break;
}
}
// Placing right pointer
// On its correct position
for (int i = N - 1; i >= 0; i--) {
if (arr[i] == maxele) {
right = i;
break;
}
}
int ans = (N / 2) - (right - left);
if (ans <= 0) {
return 0;
}
else {
return ans;
}
}
// Driver Code
int main()
{
int arr[] = { 3, 3, 5, 3, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << find(arr, N);
return 0;
}
Java
// Java program for the above approach.
import java.io.*;
class GFG {
// Function to find the number of cyclic shifts
static int find(int arr[], int N)
{
int maxele = Integer.MIN_VALUE;
for(int i = 0; i < N; i++){
maxele = Math.max(arr[i], maxele);
}
int left = -1;
int right = -1;
// Placing left pointer
// On its correct position
for (int i = 0; i < N; i++) {
if (arr[i] == maxele) {
left = i;
break;
}
}
// Placing right pointer
// On its correct position
for (int i = N - 1; i >= 0; i--) {
if (arr[i] == maxele) {
right = i;
break;
}
}
int ans = (N / 2) - (right - left);
if (ans <= 0) {
return 0;
}
else {
return ans;
}
}
// Driver Code
public static void main (String[] args) {
int arr[] = { 3, 3, 5, 3, 3, 3 };
int N = arr.length;
// Function call
System.out.print(find(arr, N));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach # Function to find the number of cyclic shifts def find(arr, N): maxele = max(arr) left = -1 right = -1 # Placing left pointer # On its correct position for i in range(N): if (arr[i] == maxele): left = i break # Placing right pointer # On its correct position for i in range(N - 1, -1, -1): if (arr[i] == maxele): right = i break ans = (N // 2) - (right - left) if (ans <= 0): return 0 else: return ans # Driver Code arr = [3, 3, 5, 3, 3, 3] N = len(arr) # Function call print(find(arr, N)) # This code is contributed by shinjanpatra
C#
// C# program for the above approach.
using System;
class GFG {
// Function to find the number of cyclic shifts
static int find(int[] arr, int N)
{
int maxele = Int32.MinValue;
for (int i = 0; i < N; i++) {
maxele = Math.Max(arr[i], maxele);
}
int left = -1;
int right = -1;
// Placing left pointer
// On its correct position
for (int i = 0; i < N; i++) {
if (arr[i] == maxele) {
left = i;
break;
}
}
// Placing right pointer
// On its correct position
for (int i = N - 1; i >= 0; i--) {
if (arr[i] == maxele) {
right = i;
break;
}
}
int ans = (N / 2) - (right - left);
if (ans <= 0) {
return 0;
}
else {
return ans;
}
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 3, 5, 3, 3, 3 };
int N = arr.Length;
// Function call
Console.Write(find(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the number of cyclic shifts
function find(arr, N) {
let maxele = Math.max([...arr]);
let left = -1;
let right = -1;
// Placing left pointer
// On its correct position
for (let i = 0; i < N; i++) {
if (arr[i] == maxele) {
left = i;
break;
}
}
// Placing right pointer
// On its correct position
for (let i = N - 1; i >= 0; i--) {
if (arr[i] == maxele) {
right = i;
break;
}
}
let ans = Math.floor(N / 2) - (right - left);
if (ans <= 0) {
return 0;
}
else {
return ans;
}
}
// Driver Code
let arr = [3, 3, 5, 3, 3, 3];
let N = arr.length;
// Function call
document.write(find(arr, N));
// This code is contributed by Potta Lokesh
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sauarbhyadav y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA