1
$\begingroup$

I am adding a small program of two loops where i am getting problem ,I know this is not legal here but this was necessary to introduce my problem .Although i have linked the detailed explanation of my problem with solution.

Best solution : For the sake of better understanding, let’s assume any bit of an element is represented by the variable ‘i’ and the variable ‘sum’ is used to store the final sum.

The idea here is, we will try to find the number of XOR values with ith bit set. Let us suppose, there are ‘Si‘ number of sub-arrays with ith bit set. For, ith bit, sum can be updated as sum += (2i * S) .

So, the question is how to implement the above idea?

We will break the task to multiple steps. At each step, we will try to find the number of XOR values with ith bit set. Now, we will break each step to sub-steps. In each sub-step, we will try to find the number of sub-arrays staring from an index ‘j'(where j varies between 0 to n – 1) with ith bit set in there XOR value. For, ith bit is to be set, odd number of elements of the sub-array should have there ith bit set. For all the bits, in a variable c_odd, we will store the count of the number of sub-arrays starting from j = 0 with ith bit set in odd number of elements. Then, we will iterate through all the elements of the array updating the value of c_odd when needed. If we reach an element ‘j’ with ith bit set, we will update c_odd as c_odd = (n – j – c_odd). Its because, since we encountered a set bit, number of sub-arrays with even number of elements with ith bit set will switch to number of sub-arrays with odd number of elements with ith bit set.

In the implementation of above approach here I am not getting below two loops are considering which part of the test case,I mean how these two loops covering all possibilities . Please can someone help me with detailed example.

problem link xor subbarray

    // loop to calculate initial 
     // value of c_odd 
     for (int j = 0; j < n; j++) { 
          if ((arr[j] & (1 << i)) > 0) 
                odd = (!odd); 
            if (odd) 
                c_odd++; 
     } 

and this one

     for (int j = 0; j < n; j++) { 
            sum += (mul * c_odd); 

            if ((arr[j] & (1 << i)) > 0) 
                c_odd = (n - j - c_odd); 
       } 
$\endgroup$
  • $\begingroup$ It is perfectly "legal" to provide a (short) program in a widespread programming langage (such is the case) whenever it helps to the description of the issue. $\endgroup$ – Jean Marie Apr 29 at 6:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.