Dado un arreglo arr[] que consta de N enteros, la tarea es realizar operaciones de desplazamiento a la derecha en los elementos del arreglo para convertir el arreglo dado en un arreglo bitónico .
Ejemplos:
Entrada: arr[] = {7, 3, 4, 5, 3}
Salida: 56 96 128 80 48
Explicación:
Realice la operación en los elementos de la array como:
- 7 → 00000111 → 3 desplazamientos a la derecha → 00111000 → 56
- 3 → 00000011 → 5 desplazamientos a la derecha → 01100000 → 96
- 4 → 00000100 → 5 desplazamientos a la derecha → 10000000 → 128
- 5 → 00000101 → 4 desplazamientos a la derecha → 01010000 → 80
- 3 → 00000011 → 4 desplazamientos a la derecha → 00110000 → 48
Después de las operaciones anteriores, la array modificada es {56, 96, 128, 80, 48}, que es una array bitónica.
Entrada: arr[] = {255, 243, 23, 141, 46}
Salida: -1
Enfoque: siga los pasos dados para resolver el problema
- Maximice el elemento central de la array , es decir, arr[N / 2] , utilizando operaciones de desplazamiento a la derecha.
- Recorra la array dada arr[], convierta la primera mitad de la array en ascendente realizando operaciones de desplazamiento a la derecha en el elemento de la array (si es necesario).
- Recorra la array dada arr[], convierta la segunda mitad de la array en orden descendente mediante operaciones de desplazamiento a la derecha en el elemento de la array (si es necesario).
- Después de completar los pasos anteriores, verifique si la array es bitónica o no . Luego imprima la array arr[] como la array resultante.
- De lo contrario, imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program for the above approach # Function to check if an # array arr[] is Bitonic or not def isPeak(arr): # Traverse the first half of arr[] for i in range(len(arr)//2, len(arr)-1): if arr[i] < arr[i + 1]: return False # Traverse the second half of arr[] for i in range(len(arr)//2): if arr[i] > arr[i + 1]: return False # Return true if arr[] is bitonic return True # Function to maximize the value of N # by performing right shift operations def maximize(n): Ele = n ans = n for idx in range(7): # Right shift by 1 if Ele & 1: Ele >>= 1 Ele += 2**32 else: Ele >>= 1 # Update the value of ans ans = max(ans, Ele) return ans # Function to arrange array in descending # order by right shift operations def makeDec(arr): # Maximise the array arr[0] prev = maximize(arr[0]) arr[0] = prev # Iterate through array arr[] for i in range(1, len(arr)): optEle = arr[i] # Flag to find the first # element less than prev flag = True # Update Ele as arr[i] Ele = arr[i] for idx in range(7): # Right shift by 1 if Ele & 1: Ele >>= 1 Ele += 2**32 else: Ele >>= 1 if Ele < prev and flag: # Update the optEle optEle = Ele # Unset the flag flag = False if Ele < prev: # Update the optEle optEle = max(optEle, Ele) # Update the array arr[i] arr[i] = optEle # Update the value of prev prev = arr[i] # Return the array return arr # Function to find the peak # element of the array arr[] def makePeak(arr): # First half of the array first = arr[:len(arr)//2 + 1] first.reverse() # Second half of the array second = arr[len(arr)//2:] # Merg both halves ans = makeDec(first)[::-1] + makeDec(second)[1:] # Function Call if isPeak(ans): return ans return -1 # Driver Code # Given array arr = [7, 3, 4, 5, 3] # Function Call print(makePeak(arr))
[1879048192, 3221225472, 4294967296, 2684354560, 1610612736]
Complejidad de tiempo: O(N * log(M)), donde M es el elemento máximo de arr[] .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA