Найдите сумму XNOR всех неупорядоченных пар из данного массива

Учитывая массив arr[] размера N , задача состоит в том, чтобы найти сумму всех значений XNOR всех возможных неупорядоченных пар из данного массива.

Примеры:

Input: N = 5, arr[] = {2, 2, 2, 1, 1}
Output:10
Explanation: Here, 
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, Therefore sum is 3+3+3+1=10.

Input: N = 3, arr[] = {1, 2, 3}
Output: 3
Explanation: Here, 1 XNOR 2 = 0, 1 XNOR 3 = 1, 2 XNOR 3 = 2. Therefore sum is 0+1+2 = 3

Подход: Единственный возможный случай установки бита после операции XNOR состоит в том, что оба бита должны быть одинаковыми . Выполните следующие шаги, чтобы решить проблему:

• Поддерживайте битовый массив размером 30. 0 -я позиция слева означает, что 2^29 включено в двоичное представление &, 29 -я позиция слева означает, что 2^0 включено в двоичное представление.
• Для каждого элемента, если установлен i -й бит , увеличивается i-я позиция битового массива.
• После обнаружения MSB , содержащего «1», вычислите биты «0» и «1».
• Пока не встретится бит «1» , все биты «0» будут потрачены впустую. Храните их отдельно.
• Наконец, предположим, что для i-й позиции имеется y единиц . Следовательно, существует y*(y-1)/2 пар для i-го бита, имеющего комбинацию битов (1, 1), которая дает результат 1 как XNOR . Кроме того, скажем, до той же позиции есть x нулей . Следовательно, существует y*(y-1)/2 пар для i-го бита, имеющего комбинацию битов (0, 0), которая дает результат 1 как XNOR .
• Теперь для случая начальных нулей умножьте количество потерянных битов на количество нулевых битов . Сделайте это для каждой битовой позиции и рассчитайте ответ.

Для лучшего понимания рассмотрим массив {35, 42, 27, 69} . Вот двоичные представления всех четырех элементов массива.

• Единица со стрелкой — это первый бит этого элемента, который равен 1. Следовательно, это самый значащий бит для этого элемента. Точно так же MSB для всех остальных элементов окрашен в зеленый цвет .
• Нули, стоящие перед старшим битом, считаются потерянными битами и окрашены в красный цвет . Размер этих бинарных массивов равен 30 каждый.
• В первых 23 позициях массива битов количество потерянных битов равно четырем , а количество единиц равно нулю , а количество нулей равно нулю , как показано на рисунке.
• В 24-й позиции потерянные биты равны 3 , а количество единиц будет равно 1 , поскольку MSB встречается в 24-м элементе элемента 69.

23rd bit: No. of wasted bits: 4, No. of 1’s: 0, No.of 0’s: 0
24th bit: No. of wasted bits: 3, No. of 1’s: 1, No.of 0’s: 0
25th bit: No. of wasted bits: 1, No. of 1’s: 2, No.of 0’s: 1 ( since it occurs after MSB )
26th bit: No. of wasted bits: 0, No. of 1’s: 1, No.of 0’s: 3
27th bit: No. of wasted bits: 0, No. of 1’s: 2, No.of 0’s: 2
28th bit: No. of wasted bits: 0, No. of 1’s: 1, No.of 0’s: 3
29th bit: No. of wasted bits: 0, No. of 1’s: 3, No.of 0’s: 1
30th bit: No. of wasted bits: 0, No. of 1’s: 3, No.of 0’s: 1

• Теперь в каждом из этих битов, чтобы значение XNOR было равно 1 в любой из пар битов, либо оба должны быть 1 , либо оба должны быть 0 .
• Поскольку оба должны быть 1 , у него есть N[i]*(N[i]-1)/2 пар, где N[i] — количество единиц в i-й позиции во всех элементах.
• Точно так же, поскольку оба должны быть 0 , он имеет M[i]*(M[i]-1)/2 пар, где M[i] — количество нулей в i-й позиции во всех элементах. Так как искомый ответ есть сумма всех возможностей. Итак, для i -го бита добавьте 2^(30-i-1) для всех возможных пар.
• В случае, если оба должны быть равны 0, также учитывайте потерянные биты , которые встречаются там, где любой из элементов имеет 0 (не потраченные впустую) в той же позиции потерянных битов. Пусть потерянные биты будут W[i] .
• Таким образом, общая сумма = (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))), где 0<= i <=30.
• Итак, для приведенного выше примера до 23-го бита все равно 0. С 24-го бита указано здесь.
• Итого = ((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)
• всего = 0 + 0 + 0 + 32 + 0 + 32 + 0 + 48 + 0 + 8 + 8 + 0 + 0 + 12 + 0 + 6 + 0 + 0 + 3 + 0 + 0
• Следовательно, общая сумма = 149

Ниже приведена реализация описанного выше подхода.

Временная сложность : O(30*N)
Вспомогательное пространство: O(1)