CODEWITHSUNDEEP
algorithmmathbit-manipulationbitwise-xor
Sumit verma
Sumit verma

Reputation: 11

Resultant sum of an array when each element is XORed by any constant

Given an array say nums = {1,2,3} and a constant C = 4 , The task is to find the sum of array elements where every element is first XORed by a constant C .

Result : (1⊕ 4) + (2 ⊕ 4) + (3 ⊕ 4) = 18

When we have only one constant then it can be done easily but What if we have K such constants then how can we find the above result ?

Example : nums = {1,2,3} Constants = 4 , 5 , 6 Then for each Constants(queries) , we need to evaluate the answer.

Upvotes: 1

Views: 81

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58409

Assuming all input numbers and the constant C are less than 2^K (perhaps K=32 or K=64), for each i from 0 to K-1, count the number of input numbers that have a 1 in bit i. Call these counts x[0], x[1], ..., x[K-1] Suppose there are N input numbers.

Let C be a given constant. Let x[i]' be x[i] if the i'th bit of C is 0, otherwise N-x[i].

Then the sum of the input numbers xored by C is sum(2^i * x[i]', i=0..K-1).

This takes O(NK) time to prepare, and O(K) time for each query.

For example, if the input is {1, 2, 3}, then there's two numbers with bit 0 set (ie: 1 and 3), and two numbers with bit 1 set (ie: 2 and 3). Let K=3, so x is {2, 2, 0}.

If C=4, then x' is {2, 2, 3-0} = {2, 2, 3}. The sum is 2 + 2*2 + 4*3 = 18.

Upvotes: 1

Related Questions