Dada una array arr[] que consta de N enteros, la tarea es encontrar el número total de subsecuencias distintas que tienen equivalencia binaria .
Una subsecuencia tiene equivalencia binaria si la suma del recuento de bits activados y desactivados en las representaciones binarias de todos los números decimales de la subsecuencia es igual.
Ejemplos:
Entrada: arr[] = {2, 7, 10}
Salida: 0011
Explicación:
2 → 0010→1’s = 1, 0’s = 3
7 → 0111→1’s = 3, 0’s = 1
10 → 1010→1’s = 2, 0’s = 2
La subsecuencia [2, 7, 10] tiene equivalencia binaria porque el número de 0 y 1 en la subsecuencia es 6 cada uno.
De manera similar, [2, 7] también tiene una equivalencia binaria de 4 cada uno.
Pero [7, 10] no tiene equivalencia binaria.
Asimismo, [10] tiene una equivalencia binaria de 2 cada uno.
El número total de subsecuencias únicas donde la equivalencia binaria es posible es 3.
Dado que 10 es el elemento más grande en la array dada y el número de bits necesarios para representar 10 en binario es 4. Por lo tanto, el número de bits presentes en la salida debe ser ser 4.Entrada: arr[] = { 5, 7, 9, 12}
Salida: 0111
Enfoque: La idea es encontrar el número total de bits necesarios para representar el elemento máximo de la array . Siga estos pasos para resolver este problema:
- Encuentre el elemento máximo y la longitud de la representación binaria del elemento máximo.
- Agregue 0 al frente de otros elementos en representación binaria , para que el número de bits en cada elemento sea igual al número máximo de bits.
- Encuentre todas las subsecuencias de la array dada .
- Encuentre el número total de subsecuencias que tienen equivalencia binaria .
- Convierta el número total en binario y agregue ceros si la longitud del número total es menor que la longitud del número máximo para que ambas longitudes sean iguales.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program for the above approach
import itertools
# Function to find the number of
# subsequences having Binary Equivalence
def numberOfSubsequence(arr):
# Find the maximum array element
Max_element = max(arr)
# Convert the maximum element
# to its binary equivalent
Max_Binary = "{0:b}".format(int(
Max_element))
# Dictionary to store the count of
# set and unset bits of all array elements
Dic = {}
for i in arr:
Str = "{0:b}".format(int(i))
if len(Str) <= len(Max_Binary):
diff = len(Max_Binary)-len(Str)
# Add the extra zeros before all
# the elements which have length
# smaller than the maximum element
Str = ('0'*diff)+Str
zeros = Str.count('0')
ones = Str.count('1')
# Fill the dictionary with number
# of 0's and 1's
Dic[int(i)] = [zeros, ones]
all_combinations = []
# Find all the combination
for r in range(len(arr)+1):
comb = itertools.combinations(arr, r)
comlist = list(comb)
all_combinations += comlist
count = 0
# Find all the combinations where
# sum_of_zeros == sum_of_ones
for i in all_combinations[1:]:
sum0 = 0
sum1 = 0
for j in i:
sum0 += Dic[j][0]
sum1 += Dic[j][1]
# Count the total combinations
# where sum_of_zeros = sum_of_ones
if sum0 == sum1:
count += 1
# Convert the count number to its
# binary equivalent
Str = "{0:b}".format(int(count))
if len(Str) <= len(Max_Binary):
diff = len(Max_Binary)-len(Str)
# Append leading zeroes to
# the answer if its length is
# smaller than the maximum element
Str = ('0'*diff) + Str
# Print the result
print(Str)
# Driver Code
# Give array arr[]
arr = [5, 7, 9, 12]
# Function Call
numberOfSubsequence(arr)
0111
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por poulami21ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA