We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The xor-sum of an array can be at most 2^(log2(max(Ai)) + 1) - 1.
Wow. That's a messy formula. Let's try to break it down. I'm assuming you know that taking log2(k) yields the number of bits used to represent k. We start with the largest element in an array call it Ai. If we xor elements that are less than Ai, the largest the xor-sum can be is when all of its bits are set. Example, Ai is the largest element in an array say 1010 (binary), since all other elements are less than or at most equivalient to Ai, we can only set or unset the bits of 1010 (we cannot add more bits since this would be a larger number but this is a contradiction since Ai max). In the max possible case, all bits of Ai are set (ex. 1010 ^ 0100 ^ 0001 = 1111) and it can never exceed that.
So what is this number exactly? Well how do we set all bits in a binary string? Set the next most significant bit and subtract 1 from it. In our example 2^(log2(1010)+1) - 1 => 2^(4+1) - 1 = 1111 or in general 2^(log(2(k)+1) -1. That's how you derive the formula.
Now in back to the problem, Ai will be at most 4500 stated in the constraints. Plug into formula 2^(log2(4500)+1) - 1 = 2^(12+1) - 1 = 2^13 - 1 = 8191. We won't need more than this many states to find the max xor-sum in any given array because it will never exceed this amount!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Prime XOR
You are viewing a single comment's thread. Return to all comments →
The xor-sum of an array can be at most 2^(log2(max(Ai)) + 1) - 1.
Wow. That's a messy formula. Let's try to break it down. I'm assuming you know that taking log2(k) yields the number of bits used to represent k. We start with the largest element in an array call it Ai. If we xor elements that are less than Ai, the largest the xor-sum can be is when all of its bits are set. Example, Ai is the largest element in an array say 1010 (binary), since all other elements are less than or at most equivalient to Ai, we can only set or unset the bits of 1010 (we cannot add more bits since this would be a larger number but this is a contradiction since Ai max). In the max possible case, all bits of Ai are set (ex. 1010 ^ 0100 ^ 0001 = 1111) and it can never exceed that.
So what is this number exactly? Well how do we set all bits in a binary string? Set the next most significant bit and subtract 1 from it. In our example 2^(log2(1010)+1) - 1 => 2^(4+1) - 1 = 1111 or in general 2^(log(2(k)+1) -1. That's how you derive the formula.
Now in back to the problem, Ai will be at most 4500 stated in the constraints. Plug into formula 2^(log2(4500)+1) - 1 = 2^(12+1) - 1 = 2^13 - 1 = 8191. We won't need more than this many states to find the max xor-sum in any given array because it will never exceed this amount!