CODEWITHSUNDEEP
algorithmbit-manipulationxor
Klasen
Klasen

Reputation: 159

XOR of numbers = X

I found this problem in a hiring contest(which is over now). Here it is:

You are given two natural numbers N and X. You are required to create an array of N natural numbers such that the bitwise XOR of these numbers is equal to X. The sum of all the natural numbers that are available in the array is as minimum as possible.

If there exist multiple arrays, print the smallest one

Array A< Array B if
A[i] < B[i] for any index i, and A[i]=B[i] for all indices less than i

Sample Input: N=3, X=2

Sample output : 1 1 2

Explanation: We have to print 3 natural numbers having the minimum sum Thus the N-spaced numbers are [1 1 2]

My approach: If N is odd, I put N-1 ones in the array (so that their xor is zero) and then put X

If N is even, I put N-1 ones again and then put X-1(if X is odd) and X+1(if X is even)

But this algorithm failed for most of the test cases. For example, when N=4 and X=6 my output is
1 1 1 7 but it should be 1 1 2 4

Anyone knows how to make the array sum minimum?

Upvotes: 4

Views: 1602

Answers (2)

Zoomba
Zoomba

Reputation: 1806

In order to have the minimum sum, you need to make sure that when your target is X, you are not cancelling the bits of X and recreating them again. Because this will increase the sum. For this, you have create the bits of X one by one (ideally) from the end of the array. So, as in your example of N=4 and X=6 we have: (I use ^ to show xor)

X= 7 = 110 (binary) = 2 + 4. Note that 2^4 = 6 as well because these numbers don't share any common bits. So, the output is 1 1 2 4.

So, we start by creating the most significant bits of X from the end of the output array. Then, we also have to handle the corner cases for different values of N. I'm going with a number of different examples to make the idea clear:

``
 A) X=14, N=5:
    X=1110=8+4+2. So, the array is 1 1 2 4 8.
 B) X=14, N=6:
    X=8+4+2. The array should be 1 1 1 1 2 12.
 C) X=15, N=6:
    X=8+4+2+1. The array should be 1 1 1 2 4 8.
 D) X=15, N=5:
    The array should be 1 1 1 2 12.
 E) X=14, N=2:
   The array should be 2 12. Because 12 = 4^8
``

So, we go as follows. We compute the number of powers of 2 in X. Let this number be k.

Case 1 - If k <= n (example E): we start by picking the smallest powers from left to right and merge the remaining on the last position in the array.

Case 2 - If k > n (example A, B, C, D): we compute h = n - k. If h is odd we put h = n-k+1. Now, we start by putting h 1's in the beginning of the array. Then, the number of places left is less than k. So, we can follow the idea of Case 1 for the remaining positions. Note that in case 2, instead of having odd number of added 1's we put and even number of 1's and then do some merging at the end. This guarantees that the array is the smallest it can be.

Upvotes: 5

Arjun Singh
Arjun Singh

Reputation: 387

We have to consider that we have to minimize the sum of the array for solution and that is the key point. First calculate set bits in N suppose if count of setbits are less than or equal to X then divide N in X integers based on set bits like

N = 15, X = 2
setbits in 15 are 4 solution is 1 14

if X = 3
solution is 1 2 12 this minimizes array sum too.

other case if setbits are greater than X
calculate difference = setbits(N) - X
If difference is even then add ones as needed and apply above algorithm all ones will cancel out.
If difference is odd then add ones but now you have take care of that 1 extra one in the answer array. Check for the corner cases too.

Upvotes: 0

Related Questions