why total numbers should be greater than equal to 130, why only pair 1-2,3-4 and so on is taken, why not 1-2, 2-3,3-4 and so on. by this logic, we will only need 66 numbers to generate 65 pairs. rather than 130 numbers?
Gray similar code problem
@rjra2611
Yes you can pick just 66 numbers to get 65 pairs
This was just an example of taking 130 numbers
thanks for the reply, @Aarnav-Jindal-1059677350830863
but in the codechef editorial the solution state that numbers should be >=130 to find 4 numbers with xor 0.
from what i am able to understand i think the condition should be >= 66 numbers.
thank you
@rjra2611
The thing is
After 130 numbers you definitely have an answer
If numbers are less than 130 like 66 you might get 65 pairs but it might happen that the A[1]^A[2] and A[2]^A[3] give the same value in which case this can’t be our answer
So the thing is
If you have >=130 numbers your answer is sure
Else you can just do brute force approach
@Aarnav-Jindal-1059677350830863
if A[1]^A[2] and A[2]^A[3] give the same value then wouldn’t it imply that A[1] == A[3] ?
If in any question it states that all the numbers are distinct then I suppose 66 would be right?
@rjra2611
Yes in case all numbers are distinct then it works
Otherwise it can fail as you mentioned yourself.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.