Convierta una array en una array bitónica desplazando a la derecha los elementos de la array

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))
Producción:

[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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *