Count all possible pairs in an array with even XOR greater than 2
Clash Royale CLAN TAG#URR8PPP
up vote
-2
down vote
favorite
Given an array $A_1,A_2, dots, A_N$. We have to tell how many pairs $(i, j)$ exist such that $1 leq i < j leq N$ and $A_i textXOR A_j$ is an even number greater than 2.
I want an $mathcalO(N)$ algorithm or at worst an $mathcalO(Nlog N)$ algorithm. Here, $N$ can be up to $10^5$.
combinatorics algorithms
asked Sep 10 at 7:37
tanweer anwar
13
 |Â
show 1 more comment
up vote
-2
down vote
favorite
Given an array $A_1,A_2, dots, A_N$. We have to tell how many pairs $(i, j)$ exist such that $1 leq i < j leq N$ and $A_i textXOR A_j$ is an even number greater than 2.
I want an $mathcalO(N)$ algorithm or at worst an $mathcalO(Nlog N)$ algorithm. Here, $N$ can be up to $10^5$.
combinatorics algorithms
asked Sep 10 at 7:37
tanweer anwar
13
1
In other words, $A_i$ and $A_j$ are either equal, or differ only in ther second-lowest bit?
– Hagen von Eitzen
Sep 10 at 8:04
"is an even no greater than 2": as far as I know, this means 0 or 2. Please confirm.
– Yves Daoust
Sep 10 at 8:10
@YvesDaoust even no except 0 or 2
– tanweer anwar
Sep 10 at 8:15
@tanweeranwar: please write in unambiguous English.
– Yves Daoust
Sep 10 at 8:17
@tanweeranwar - do you mean an even number that is "no greater than 2" i.e. 0 or 2 - or do you mean an even number (abbreviated "no") that is greater than 2 i.e. 4,6,8, etc.
– gandalf61
Sep 10 at 8:40
 |Â
show 1 more comment
up vote
-2
down vote
favorite
up vote
-2
down vote
favorite
Given an array $A_1,A_2, dots, A_N$. We have to tell how many pairs $(i, j)$ exist such that $1 leq i < j leq N$ and $A_i textXOR A_j$ is an even number greater than 2.
I want an $mathcalO(N)$ algorithm or at worst an $mathcalO(Nlog N)$ algorithm. Here, $N$ can be up to $10^5$.
combinatorics algorithms
asked Sep 10 at 7:37
tanweer anwar
13
Given an array $A_1,A_2, dots, A_N$. We have to tell how many pairs $(i, j)$ exist such that $1 leq i < j leq N$ and $A_i textXOR A_j$ is an even number greater than 2.
I want an $mathcalO(N)$ algorithm or at worst an $mathcalO(Nlog N)$ algorithm. Here, $N$ can be up to $10^5$.
combinatorics algorithms
combinatorics algorithms
asked Sep 10 at 7:37
tanweer anwar
13
asked Sep 10 at 7:37
tanweer anwar
13
edited Sep 10 at 10:12
asked Sep 10 at 7:37
tanweer anwar
13
asked Sep 10 at 7:37
tanweer anwar
13
asked Sep 10 at 7:37
tanweer anwar
13
13
1
In other words, $A_i$ and $A_j$ are either equal, or differ only in ther second-lowest bit?
– Hagen von Eitzen
Sep 10 at 8:04
"is an even no greater than 2": as far as I know, this means 0 or 2. Please confirm.
– Yves Daoust
Sep 10 at 8:10
@YvesDaoust even no except 0 or 2
– tanweer anwar
Sep 10 at 8:15
@tanweeranwar: please write in unambiguous English.
– Yves Daoust
Sep 10 at 8:17
@tanweeranwar - do you mean an even number that is "no greater than 2" i.e. 0 or 2 - or do you mean an even number (abbreviated "no") that is greater than 2 i.e. 4,6,8, etc.
– gandalf61
Sep 10 at 8:40
 |Â
show 1 more comment
1
In other words, $A_i$ and $A_j$ are either equal, or differ only in ther second-lowest bit?
– Hagen von Eitzen
Sep 10 at 8:04
"is an even no greater than 2": as far as I know, this means 0 or 2. Please confirm.
– Yves Daoust
Sep 10 at 8:10
@YvesDaoust even no except 0 or 2
– tanweer anwar
Sep 10 at 8:15
@tanweeranwar: please write in unambiguous English.
– Yves Daoust
Sep 10 at 8:17
@tanweeranwar - do you mean an even number that is "no greater than 2" i.e. 0 or 2 - or do you mean an even number (abbreviated "no") that is greater than 2 i.e. 4,6,8, etc.
– gandalf61
Sep 10 at 8:40
1
1
In other words, $A_i$ and $A_j$ are either equal, or differ only in ther second-lowest bit?
– Hagen von Eitzen
Sep 10 at 8:04
In other words, $A_i$ and $A_j$ are either equal, or differ only in ther second-lowest bit?
– Hagen von Eitzen
Sep 10 at 8:04
"is an even no greater than 2": as far as I know, this means 0 or 2. Please confirm.
– Yves Daoust
Sep 10 at 8:10
"is an even no greater than 2": as far as I know, this means 0 or 2. Please confirm.
– Yves Daoust
Sep 10 at 8:10
@YvesDaoust even no except 0 or 2
– tanweer anwar
Sep 10 at 8:15
@YvesDaoust even no except 0 or 2
– tanweer anwar
Sep 10 at 8:15
@tanweeranwar: please write in unambiguous English.
– Yves Daoust
Sep 10 at 8:17
@tanweeranwar: please write in unambiguous English.
– Yves Daoust
Sep 10 at 8:17
@tanweeranwar - do you mean an even number that is "no greater than 2" i.e. 0 or 2 - or do you mean an even number (abbreviated "no") that is greater than 2 i.e. 4,6,8, etc.
– gandalf61
Sep 10 at 8:40
@tanweeranwar - do you mean an even number that is "no greater than 2" i.e. 0 or 2 - or do you mean an even number (abbreviated "no") that is greater than 2 i.e. 4,6,8, etc.
– gandalf61
Sep 10 at 8:40
 |Â
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Â
draft saved
draft discarded
Â
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2911641%2fcount-all-possible-pairs-in-an-array-with-even-xor-greater-than-2%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
In other words, $A_i$ and $A_j$ are either equal, or differ only in ther second-lowest bit?
– Hagen von Eitzen
Sep 10 at 8:04
"is an even no greater than 2": as far as I know, this means 0 or 2. Please confirm.
– Yves Daoust
Sep 10 at 8:10
@YvesDaoust even no except 0 or 2
– tanweer anwar
Sep 10 at 8:15
@tanweeranwar: please write in unambiguous English.
– Yves Daoust
Sep 10 at 8:17
@tanweeranwar - do you mean an even number that is "no greater than 2" i.e. 0 or 2 - or do you mean an even number (abbreviated "no") that is greater than 2 i.e. 4,6,8, etc.
– gandalf61
Sep 10 at 8:40