Dada una array A[] de tamaño N con entradas como números enteros, algunas de las entradas son -1. La tarea es reemplazar los -1 con números que satisfagan los siguientes criterios.
- La representación binaria del número que se va a reemplazar debe tener solo 0 en sus posiciones impares y el número debe ser par.
- Las entradas de array A[i] con las que se reemplazan los -1 son de tal manera que A[i]>=A[i-1] y también para la array dada A[0]!=-1 .
Encuentre la suma mínima de entradas de array posible después de realizar las operaciones anteriores.
Ejemplos:
Entrada: A[] = {1, 5, -1, 25, -1, 7, 35, -1}
Salida: 153
Índice 2: Reemplazar -1 con 8 ya que su representación binaria es 1000 que tiene 0
en sus lugares impares y 8 es par y 8 >=5
Índice 4: Reemplazar -1 con 32 como su representación binaria es 100000 que tiene 0
en sus lugares impares y 32 es par y 32>=25
Índice 7: Reemplazar -1 con 40 como su binario la representación es 101000 que tiene 0
en sus lugares impares y 40 es par y 40>=35Entrada: A[] = {4, 8, 12, -1, 3, 0, 15, -1, 34, -1}
Salida: 142
Acercarse:
- Iterar a través de una array utilizando la búsqueda lineal para identificar todos los -1.
- Dondequiera que haya -1, generar otro ciclo while a partir del número que está en un índice 1 menor que el índice actual.
- Verifique las posiciones impares de las representaciones binarias de todos los términos en progresión y si contiene solo ceros como se esperaba, salga del ciclo; de lo contrario, incremente el iterador en 1 hasta que alcancemos el número requerido.
- Cuando se cumple el número requerido, el elemento correspondiente en el índice dado se reemplaza con el nuevo número encontrado que cumple todas las condiciones.
- Calcule la suma de las entradas de la array después de reemplazar todos los -1.
A continuación se muestra la implementación del enfoque anterior:
# Find the minimum sum of array # entries following given criteria. def Bit_Even_Arrays(arr): # Iterating through the # array to find -1's for k, v in enumerate(arr): z = 0 if v == -1: # Starting from the entry # with index 1 less than -1 # as A[i]>= A[i-1] y = k - 1 z = arr[y] # Initiating the infinite series # that satisfies given criteria # and breaking out of the loop # once it satisfies while True: S = bin(z)[2:][1::2] if (z % 2 == 0) \ &(len(set(S))== 1)\ & ('0' in set(S)): break else: # incrementing the entry # until the required # entry is met z += 1 arr[k]= z return (sum(arr)) # Driver code if __name__ == '__main__': arr = [1, 5, -1, 25, -1, 7, 35, -1] print (Bit_Even_Arrays(arr))
153
Publicación traducida automáticamente
Artículo escrito por Vikas Chitturi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA