Dada una array arr[] de tamaño N , la tarea es encontrar la suma de todos los valores XNOR de todos los posibles pares desordenados de la array dada.
Ejemplos:
Entrada : N = 5, arr[] = {2, 2, 2, 1, 1}
Salida : 10
Explicación : Aquí,
2 XNOR 2 = 3, 2 XNOR 2 = 3, 2 XNOR 2 = 3, 1 XNOR 1 = 1, 2 XNOR 1 = 0, 2 XNOR 1 = 0, 2 XNOR 1 = 0, 2 XNOR 1 = 0, 2 XNOR 1 = 0, 2 XNOR 1 = 0, Por lo tanto, la suma es 3+3+3+1=10 .Entrada : N = 3, arr[] = {1, 2, 3}
Salida : 3
Explicación : Aquí, 1 XNOR 2 = 0, 1 XNOR 3 = 1, 2 XNOR 3 = 2. Por lo tanto, la suma es 0+1+2 = 3
Enfoque: el único caso posible para que se establezca un bit después de la operación XNOR es que ambos bits deben ser iguales . Siga los pasos a continuación para resolver el problema:
- Mantenga una array de bits de tamaño 30. La posición 0 desde la izquierda significa que 2^29 está incluida en la representación binaria y la posición 29 desde la izquierda significa que 2^0 está incluida en la representación binaria.
- Para cada elemento, si se establece el bit i-ésimo , incremente la posición i-ésima de la array de bits.
- Después de encontrar el MSB que contiene ‘1’, calcule los bits ‘0’ y ‘1’.
- Hasta que se encuentre un bit ‘1’ , todos los bits ‘0’ serán bits desperdiciados. Guárdelos por separado.
- Finalmente, digamos que para una i-ésima posición hay y número de unos . Por lo tanto, hay y*(y-1)/2 pares para un i-ésimo bit que tiene una combinación de bits (1, 1) que da el resultado 1 como XNOR . Además, digamos que hasta la misma posición hay x número de ceros . Por lo tanto, hay y*(y-1)/2 pares para un i-ésimo bit que tiene una combinación de bits (0, 0) que da el resultado 1 como XNOR .
- Ahora, para el caso de los ceros iniciales , multiplique el número de bits desperdiciados por el número de 0 bits . Haga esto para cada posición de bit y calcule la respuesta.
Para una mejor comprensión, considere la array {35, 42, 27, 69} . Aquí están las representaciones binarias de los cuatro elementos de la array.
Representaciones binarias de elementos de array.
- El unidireccional con la flecha es el primer bit de ese elemento que es 1. Por lo tanto, es el bit más significativo para ese elemento. De manera similar, el MSB para todos los demás elementos se colorea de verde .
- Los ceros que aparecen antes del MSB son bits perdidos y están coloreados en rojo . El tamaño de estas arrays binarias es de 30 cada una.
- En las primeras 23 posiciones de la array de bits, la cantidad de bits desperdiciados es cuatro , la cantidad de 1 es cero y la cantidad de 0 es cero , como se ve en la imagen.
- En la posición 24, los bits desperdiciados son 3 y el número de 1 será 1 , ya que se encuentra MSB en el elemento 24 del elemento 69.
Bit 23: Nº de bits desperdiciados : 4, Nº de 1 : 0, Nº de 0 : 0
Bit 24: Nº de bits desperdiciados : 3, Nº de 1 : 1, Nº de 0 : 0
Bit 25 : N.º de bits desperdiciados : 1, N.º de 1 : 2, N.º de 0 : 1 (ya que ocurre después de MSB)
Bit 26: N.º de bits desperdiciados : 0, N.º de 1 : 1, N.º de 0’s: 3
27th bit: No. de bits desperdiciados : 0, No. de 1’s : 2, No.de 0’s : 2
28th bit: No. de bits desperdiciados : 0,Nº de 1 : 1, Nº de 0 : 3
Bit 29: Nº de bits desperdiciados : 0, Nº de 1 : 3, Nº de 0 : 1
Bit 30: Nº de bits desperdiciados : 0, Nº de 1 : 3, número de 0 : 1
- Ahora, en cada uno de estos bits, para que el valor XNOR sea 1 en cualquiera de los pares de bits, ambos deben ser 1 o ambos deben ser 0 .
- Para que ambos sean 1 , tiene N[i]*(N[i]-1)/2 pares, donde N[i] es el número de 1 en la i-ésima posición en todos los elementos.
- De manera similar, para que ambos sean 0 , tiene M[i]*(M[i]-1)/2 pares, donde M[i] es el número de 0 en la i-ésima posición en todos los elementos. Dado que la respuesta requerida es la suma de todas las posibilidades. Entonces, para un i-ésimo bit, suma 2^(30-i-1) para todos los pares posibles.
- En caso de que ambos deban ser 0, considere también los bits desperdiciados que ocurren cuando alguno de los elementos tiene un 0 (no desperdiciado) en la misma posición de los bits desperdiciados. Deje que los bits desperdiciados sean W[i] .
- Entonces suma total = (N[i]*(N[i]-1)/2)*(2^(30-i-1) + (M[i]*(M[i]-1)/2) *(2^(30-i-1) + (W[i]*M[i]*(2^(30-i-1))) donde 0<= i <=30.
- Entonces, para el ejemplo anterior, hasta el bit 23, todo es 0. Desde el bit 24 se enumera aquí.
- total = ((1*0)/2)*(2^6) + ((0*(-1))/2)*(2^6) + 3*0*(2^6) + ((2 *1)/2)*(2^5) + ((1*0)/2)*(2^5) + 1*1*(2^5) + ((1*0)/2)*( 2^4) + ((3*2)/2)*(2^4) + 0*3*(2^4) + ((2*1)/2)*(2^3) + ((2 *1)/2)*(2^3) + 0*2*(2^3) + ((1*0)/2)*(2^2) + ((3*2)/2)*( 2^2) + 0*3*(2^2) + ((3*2)/2)*(2^1) + ((1*0)/2)*(2^1) + 0*1 *(2^1) + ((3*2)/2)*(2^0) + ((1*0)/2)*(2^0) + 0*1*(2^0)
- total = 0 + 0 + 0 + 32 + 0 + 32 + 0 + 48 + 0 + 8 + 8 + 0 + 0 + 12 + 0 + 6 + 0 + 0 + 3 + 0 + 0
- Por lo tanto, suma total = 149
A continuación se muestra la implementación del enfoque anterior.
Python3
# Python program for the above approach # Function to find the required sum def findSum(n, r): # Store the result result = 0 # bits[i][0] and bits[i][1] has # count of all 1's and 0's in the # ith bit of all elements respectively # bits[i][2] has count of wasted zeroes # of ith bit for all elements bits = [[0, 0, 0] for i in range(30)] # Iterating through all elements for i in r: # Converting element to binary binary = bin(i)[2:] # zfill adds zeros to the front binary = binary.zfill(30) # Flag variable set to 1 after # first occurrence of 1 (MSB) flag = 0 # Iterating through all the bits for j in range(30): # If msb not found if(flag == 0): # Msb found if(binary[j] == '1'): # Set flag to 1 flag = 1 # Incrementing number # of 1's in jth bit bits[j][0] += 1 # If msb not found yet else: # Incrementing number of # wasted zeroes before msb bits[j][2] += 1 # Continue till msb is encountered continue # Incrementing number # of 1's in jth bit if(binary[j] == '1'): bits[j][0] += 1 # Incrementing number # of 0's in jth bit else: bits[j][1] += 1 # Iterating through all bits for i in range(30): # Total number of 1's in # ith bit of all elements y = bits[i][0] # Total number of 0's in # ith bit of all elements x = bits[i][1] # Total number of wasted 0's # before msb of ith bit of all elements msboff = bits[i][2] # y*(y-1)/2 pairs for ith bit has (1, 1) # bit combo which gives result 1 in XNOR onePairs = (y*(y-1))//2 # Adding value of ith # bit number of (1, 1) pairs # times to result # (2^(30-i-1) => 2 ^ 29, 2 ^ 28 etc. result += onePairs * pow(2, 30-i-1) # x*(x-1)/2 pairs for ith bit has (0, 0) # bit combo which gives result 1 in XNOR zeroPairs = ((x*(x-1))//2) # Adding value of ith bit # number of (0, 0) pairs # times to result # (2^(30-i-1) => 2 ^ 29, 2 ^ 28 etc.) result += zeroPairs * pow(2, 30-i-1) # Same for leading zeroes result += (msboff * x)*pow(2, 30-i-1) return result # Driver code if __name__ == '__main__': n = 5 r = [2, 2, 2, 1, 1] print(findSum(n, r))
Javascript
<script>
// JavaScript program for the above approach
// Function to find the required sum
const findSum = (n, r) => {
// Store the result
let result = 0;
// bits[i][0] and bits[i][1] has
// count of all 1's and 0's in the
// ith bit of all elements respectively
// bits[i][2] has count of wasted zeroes
// of ith bit for all elements
let bits = new Array(30).fill(0).map(() => new Array(3).fill(0));
// Iterating through all elements
for (let i in r) {
// Converting element to binary
let binary = Number(r[i]).toString(2);
binary = binary.split("");
while (binary.length < 30) {
binary.unshift('0');
}
// Flag variable set to 1 after
// first occurrence of 1 (MSB)
let flag = 0;
// Iterating through all the bits
for (let j = 0; j < 30; j++) {
// If msb not found
if (flag == 0) {
// Msb found
if (binary[j] == '1') {
// Set flag to 1
flag = 1;
// Incrementing number
// of 1's in jth bit
bits[j][0] += 1;
}
// If msb not found yet
else
// Incrementing number of
// wasted zeroes before msb
bits[j][2] += 1;
// Continue till msb is encountered
continue;
}
// Incrementing number
// of 1's in jth bit
if (binary[j] == '1')
bits[j][0] += 1;
// Incrementing number
// of 0's in jth bit
else
bits[j][1] += 1;
}
}
// document.write(`${bits}<br/>`)
// Iterating through all bits
for (let i = 0; i < 30; i++) {
// Total number of 1's in
// ith bit of all elements
let y = bits[i][0];
// Total number of 0's in
// ith bit of all elements
let x = bits[i][1];
// Total number of wasted 0's
// before msb of ith bit of all elements
let msboff = bits[i][2];
// y*(y-1)/2 pairs for ith bit has (1, 1)
// bit combo which gives result 1 in XNOR
let onePairs = (y * (y - 1)) / 2;
// Adding value of ith
// bit number of (1, 1) pairs
// times to result
// (2^(30-i-1) => 2 ^ 29, 2 ^ 28 etc.
result += onePairs * Math.pow(2, 30 - i - 1);
// x*(x-1)/2 pairs for ith bit has (0, 0)
// bit combo which gives result 1 in XNOR
let zeroPairs = (x * (x - 1)) / 2;
// Adding value of ith bit
// number of (0, 0) pairs
// times to result
// (2^(30-i-1) => 2 ^ 29, 2 ^ 28 etc.)
result += zeroPairs * Math.pow(2, 30 - i - 1);
// Same for leading zeroes
result += (msboff * x) * Math.pow(2, 30 - i - 1);
}
return result;
}
// Driver code
let n = 5;
let r = [2, 2, 2, 1, 1];
document.write(findSum(n, r));
// This code is contributed by rakeshsahni
</script>
Producción
10
Complejidad de tiempo : O(30*N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vishnuthulasidosss y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA