It’s not clear why we say Yes for n >= 130
It’s clear we can use brute force method, but the pigeonhole principle is not clear.
Can anyone explain it?
And also how would I know, when to apply the pigeonhole principle.
Video Link: https://online.codingblocks.com/player/12816/content/58?s=2729
Gray SimilarCode
first thing: as array elements differ by one bit hence xor will be of from …0000…1…00…
second if i take 65 elements then i’ll get 64 kind of xor ( of adjacent elements ) in worst case.
Now in other half containing 65 elements we will similarly have 64 kind in worst case, hence their exits two pair of elements in both the halves such that xor is zero, hence if n>=130 we have 0 as answer.
Hit like if you get it.
Cheers!
1 Like
Thank you for explaining.
1 Like