- Forum
- General C++ Programming
- xor of every subarray in an array ?
xor of every subarray in an array ?
given an array with length n, with every number <= 1e6, as there are n(n+2) / 2 subarrays there will be the same number of XORs (xor of every subarray elements), is there a way to find a set containing the values of these XORs along with the number of occurences of each value in a complexity less than n^2?
Last edited on
number is array element a[i]
0 <= a[i] <= 1e6
xor is done by xoring all elements of a subarray i and getting a value vi, this is done for all subarrays. now I want to get a set containing vi values (without repetition) with the number of occurences of every vi (how many subarrays such that; for every subarray of them; the xoring of this subarray's elements with each other gives vi)
I want to achieve this in less than n^2, is it possible?
0 <= a[i] <= 1e6
xor is done by xoring all elements of a subarray i and getting a value vi, this is done for all subarrays. now I want to get a set containing vi values (without repetition) with the number of occurences of every vi (how many subarrays such that; for every subarray of them; the xoring of this subarray's elements with each other gives vi)
I want to achieve this in less than n^2, is it possible?
probably.
xor a sub-array is just O(n) where n is size of sub-array.
xor of all the sub arrays is still O(n) but n now is <= the size of the full outer array.
and making a list of values with deduplication is also O(n). Adding it all up seems to be O(n)? The easy way to handle this is with a map of {value, count}. When you try to insert a value, check if it is already there. If it is already there, increment its count. If it isn't there, put it in with count = 1.
xor a sub-array is just O(n) where n is size of sub-array.
xor of all the sub arrays is still O(n) but n now is <= the size of the full outer array.
and making a list of values with deduplication is also O(n). Adding it all up seems to be O(n)? The easy way to handle this is with a map of {value, count}. When you try to insert a value, check if it is already there. If it is already there, increment its count. If it isn't there, put it in with count = 1.
The part that is confusing me here is how to get all possible xors in less than O(n^2), the way that I thought of is maintaining array with all prefix XORs. if this array has name arr and the original array that contains the elements themselves has name a; so arr[i] will be a[0] ^ a[1] ^ ...... ^ a[i].
for each arr[i]; XOR arr[i] with each arr[j] where 0 <= j < i. the resulting XORs are XORs of subarrays ending in i, so add them to the map (or increase their count if they exist), also add arr[i] itself to the map.
but this has complexity of n^2.
for each arr[i]; XOR arr[i] with each arr[j] where 0 <= j < i. the resulting XORs are XORs of subarrays ending in i, so add them to the map (or increase their count if they exist), also add arr[i] itself to the map.
but this has complexity of n^2.
ah. That is what we needed to see. I don't think you can make this any better than N*N.
The way you stated it before sounded like ^ all the values together (like a checksum or something) in each sub array.
The only way to improve it would be if the sub-arrays overlap and repeat work, or if you see any other known repeated work to eliminate.
The way you stated it before sounded like ^ all the values together (like a checksum or something) in each sub array.
The only way to improve it would be if the sub-arrays overlap and repeat work, or if you see any other known repeated work to eliminate.
Topic archived. No new replies allowed.