CODEWITHSUNDEEP
algorithmmath
pranay
pranay

Reputation: 2369

finding total ways of XORing an array of integers to produce zero

If we have an array of integers then how can we find the number of ways that they be XORed so that the result is 0 . Here at each step only one integer(i) can be decreased by any amount say d such that (i-d)>=0 . E.g for the integers 11,15,8 we can decrease 11 to 7 so that 7^15^8 =0 . Similary 15 can be reduced to 3 such that 11^3^8 = 0 and 8 can be reduced to 4 such that 11^15^4=0 . Hence total ways is 3

My approach: to this is for each integer , go on decreasing it and at each step XOR it with remaining integers in the array , if the result is 0 , break. Check this for all integers and get the total ways. But this is 0(n^2) . Is there any efficient way to do it? Thanks.

Upvotes: 2

Views: 144

Answers (2)

shift66
shift66

Reputation: 11958

You can XOR all integers in your array, then in loop XOR the result with each of your integers (it will "remove" that integer from all because x^x is always 0). As a result you'll get XOR of the other members and that's the number to be replaced (because x^x is always 0).

    int[] a = new int [size];
    //initialize 'a' array
    int[] b = new int [size];
    int all = 0;
    for(int i = 0; i<a.length; i++)
        all=all^a[i];

    for(int i =0; i< size; i++)
        b[i] = all^a[i];

In b[i] you'll get the number to be replaced with a[i] to get zero.
I edited my answer and tried, it works. This is O(n).

Upvotes: 2

ElKamina
ElKamina

Reputation: 7807

This is very similar to finding k numbers in an array of length that sum to x.

For k=1: Obvious. Find elements that are equal to 0

For k=2: Sort the numbers and for each number a check if 0^a exists in the array

For k=3: Sort the numbers and for each pair of numbers a and b check if a^b^0 exists in the array

For k=4: Calculate xors of every two numbers in the array and sort. And for each pair of numbers a and b check if a^b^0 exists in the sorted list

so on

For k=1, complexity is O(n), k-2: nlogn, k=3: n^2logn, k=4: n^2logn and so on.

Upvotes: 0

Related Questions