Steps to solve the problem


#1

The main logic behind problems involving XOR operation is that you have to update the bits of final answer.

  1. XOR = 0 if A=B else XOR = 1, so 1^1^0^0=0, you have to find whether 1 is present even number of times or not,
  2. To check the above point, instead of doing XOR operation at each iteration, we can update the bits of final answer. I would like to explain this point with an example
    lets take A= [ 4, 5, 7, 9], so we need to find 4^5^7^9
    4= 0100
    5= 0101
    7= 0111
    9= 1001
    ans= 1313
    to find the bits at each position of answer we will simply add the corresponding bits of inputs and take mod of each value with 2, so 1313=1111 = 15 in decimal
    Thus 4^5^7^9=15. This concept to find final answer involving XOR operations is applicable on a wide range of questions.

Now coming to this question, we have to know which number will occur how many times in all the sub-arrays
answer: element at ith index will occur (i+1)*(n-i) times in total, n=size of array.
I hope this was helpful to you.
Happy coding.


#2

element at ith index will occur (i+1)*(n-i) times in total, n=size of array.

Can u explain how??


#3

yes every element occurs (i+1)(n-i)… we can see this in this way lets say we have an array [start,…i,…end] now choose any element in the array say “i”. Now we have to find all the possible subarrays which can contain this element “i” in it. So now we have choose a starting index and ending index of the sub array. for the element “i” to lie in the sub array the starting index should lie between (start…i) and ending index should lie between (i,…end). So now just choose one element from both the ranges, we will get (i+1)(n-i).