Finding minimum index of element in array range that gives maximum xor with given value
up vote
-3
down vote
favorite
We have an array(elements/numbers are given in binary form/string format) and there are multiple queries of the form:
Q(L,R,X) = smallest index i (L ≤ i ≤ R) such that
the value Arr[i]⊕X is maximum possible,
equal to max(Arr[L]⊕X,Arr[L+1]⊕X,…,Arr[R]⊕X)
See below example for clarification:
arr[5] = 11,100,101,101,1
Q(2,4,10) = 2
since arr[2]⊕10 = arr[3]⊕10
is maximum possible xor and index 2 < 3
In my approach, I have used trie data structure. While querying I do a binary search if the current node of trie has index in range [L,R] while iterating over the bits of number X from most significant bit to least significant bit(look for inverse of bits, since that only maximises the xor).
This results in answering of queries in O(length(X) * log(N)) where N is the size of array.
The difficult part is numbers in array are of different length(size of bits) and same for X in the queries. You can handle this by pre-processing(appending 0s in front of all numbers) but this increases time complexity of the solution.
Is there any faster way to do this?
algorithm optimization trie dynamic-queries
asked Nov 9 at 18:49
DEV KUMAR
63
add a comment |
up vote
-3
down vote
favorite
We have an array(elements/numbers are given in binary form/string format) and there are multiple queries of the form:
Q(L,R,X) = smallest index i (L ≤ i ≤ R) such that
the value Arr[i]⊕X is maximum possible,
equal to max(Arr[L]⊕X,Arr[L+1]⊕X,…,Arr[R]⊕X)
See below example for clarification:
arr[5] = 11,100,101,101,1
Q(2,4,10) = 2
since arr[2]⊕10 = arr[3]⊕10
is maximum possible xor and index 2 < 3
In my approach, I have used trie data structure. While querying I do a binary search if the current node of trie has index in range [L,R] while iterating over the bits of number X from most significant bit to least significant bit(look for inverse of bits, since that only maximises the xor).
This results in answering of queries in O(length(X) * log(N)) where N is the size of array.
The difficult part is numbers in array are of different length(size of bits) and same for X in the queries. You can handle this by pre-processing(appending 0s in front of all numbers) but this increases time complexity of the solution.
Is there any faster way to do this?
algorithm optimization trie dynamic-queries
asked Nov 9 at 18:49
DEV KUMAR
63
I'm interested in the problem, but can't follow the details of your approach. Could you provide a pseudo-code description of the algorithm?
– jwimberley
Nov 9 at 21:52
1
I'm assuming that the complexity you cite does not include the building of the trie (which would have to be at least O(N) times constant factor related to number of bits in each element of array), but reflects a scenario where you build a trie once and then repeatedly reuse for multiple queries Q, correct?
– jwimberley
Nov 9 at 22:07
Third and last comment for now: Does "if the current node of trie has index in range [L,R]" mean that each node in the trie includes a table of all (L,R) pairs for which there is an entry L<=idx<=R in the current node or any of its descendants?
– jwimberley
Nov 9 at 22:09
You keeping all the indexes of array in trie node, right? doen't it will require lots of memoty?
– nightfury1204
Nov 10 at 6:45
add a comment |
up vote
-3
down vote
favorite
up vote
-3
down vote
favorite
We have an array(elements/numbers are given in binary form/string format) and there are multiple queries of the form:
Q(L,R,X) = smallest index i (L ≤ i ≤ R) such that
the value Arr[i]⊕X is maximum possible,
equal to max(Arr[L]⊕X,Arr[L+1]⊕X,…,Arr[R]⊕X)
See below example for clarification:
arr[5] = 11,100,101,101,1
Q(2,4,10) = 2
since arr[2]⊕10 = arr[3]⊕10
is maximum possible xor and index 2 < 3
In my approach, I have used trie data structure. While querying I do a binary search if the current node of trie has index in range [L,R] while iterating over the bits of number X from most significant bit to least significant bit(look for inverse of bits, since that only maximises the xor).
This results in answering of queries in O(length(X) * log(N)) where N is the size of array.
The difficult part is numbers in array are of different length(size of bits) and same for X in the queries. You can handle this by pre-processing(appending 0s in front of all numbers) but this increases time complexity of the solution.
Is there any faster way to do this?
algorithm optimization trie dynamic-queries
asked Nov 9 at 18:49
DEV KUMAR
63
We have an array(elements/numbers are given in binary form/string format) and there are multiple queries of the form:
Q(L,R,X) = smallest index i (L ≤ i ≤ R) such that
the value Arr[i]⊕X is maximum possible,
equal to max(Arr[L]⊕X,Arr[L+1]⊕X,…,Arr[R]⊕X)
See below example for clarification:
arr[5] = 11,100,101,101,1
Q(2,4,10) = 2
since arr[2]⊕10 = arr[3]⊕10
is maximum possible xor and index 2 < 3
In my approach, I have used trie data structure. While querying I do a binary search if the current node of trie has index in range [L,R] while iterating over the bits of number X from most significant bit to least significant bit(look for inverse of bits, since that only maximises the xor).
This results in answering of queries in O(length(X) * log(N)) where N is the size of array.
The difficult part is numbers in array are of different length(size of bits) and same for X in the queries. You can handle this by pre-processing(appending 0s in front of all numbers) but this increases time complexity of the solution.
Is there any faster way to do this?
algorithm optimization trie dynamic-queries
algorithm optimization trie dynamic-queries
asked Nov 9 at 18:49
DEV KUMAR
63
asked Nov 9 at 18:49
DEV KUMAR
63
edited Nov 10 at 6:11
asked Nov 9 at 18:49
DEV KUMAR
63
asked Nov 9 at 18:49
DEV KUMAR
63
asked Nov 9 at 18:49
DEV KUMAR
63
63
I'm interested in the problem, but can't follow the details of your approach. Could you provide a pseudo-code description of the algorithm?
– jwimberley
Nov 9 at 21:52
1
I'm assuming that the complexity you cite does not include the building of the trie (which would have to be at least O(N) times constant factor related to number of bits in each element of array), but reflects a scenario where you build a trie once and then repeatedly reuse for multiple queries Q, correct?
– jwimberley
Nov 9 at 22:07
Third and last comment for now: Does "if the current node of trie has index in range [L,R]" mean that each node in the trie includes a table of all (L,R) pairs for which there is an entry L<=idx<=R in the current node or any of its descendants?
– jwimberley
Nov 9 at 22:09
You keeping all the indexes of array in trie node, right? doen't it will require lots of memoty?
– nightfury1204
Nov 10 at 6:45
add a comment |
I'm interested in the problem, but can't follow the details of your approach. Could you provide a pseudo-code description of the algorithm?
– jwimberley
Nov 9 at 21:52
1
I'm assuming that the complexity you cite does not include the building of the trie (which would have to be at least O(N) times constant factor related to number of bits in each element of array), but reflects a scenario where you build a trie once and then repeatedly reuse for multiple queries Q, correct?
– jwimberley
Nov 9 at 22:07
Third and last comment for now: Does "if the current node of trie has index in range [L,R]" mean that each node in the trie includes a table of all (L,R) pairs for which there is an entry L<=idx<=R in the current node or any of its descendants?
– jwimberley
Nov 9 at 22:09
You keeping all the indexes of array in trie node, right? doen't it will require lots of memoty?
– nightfury1204
Nov 10 at 6:45
I'm interested in the problem, but can't follow the details of your approach. Could you provide a pseudo-code description of the algorithm?
– jwimberley
Nov 9 at 21:52
I'm interested in the problem, but can't follow the details of your approach. Could you provide a pseudo-code description of the algorithm?
– jwimberley
Nov 9 at 21:52
1
1
I'm assuming that the complexity you cite does not include the building of the trie (which would have to be at least O(N) times constant factor related to number of bits in each element of array), but reflects a scenario where you build a trie once and then repeatedly reuse for multiple queries Q, correct?
– jwimberley
Nov 9 at 22:07
I'm assuming that the complexity you cite does not include the building of the trie (which would have to be at least O(N) times constant factor related to number of bits in each element of array), but reflects a scenario where you build a trie once and then repeatedly reuse for multiple queries Q, correct?
– jwimberley
Nov 9 at 22:07
Third and last comment for now: Does "if the current node of trie has index in range [L,R]" mean that each node in the trie includes a table of all (L,R) pairs for which there is an entry L<=idx<=R in the current node or any of its descendants?
– jwimberley
Nov 9 at 22:09
Third and last comment for now: Does "if the current node of trie has index in range [L,R]" mean that each node in the trie includes a table of all (L,R) pairs for which there is an entry L<=idx<=R in the current node or any of its descendants?
– jwimberley
Nov 9 at 22:09
You keeping all the indexes of array in trie node, right? doen't it will require lots of memoty?
– nightfury1204
Nov 10 at 6:45
You keeping all the indexes of array in trie node, right? doen't it will require lots of memoty?
– nightfury1204
Nov 10 at 6:45
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53231702%2ffinding-minimum-index-of-element-in-array-range-that-gives-maximum-xor-with-give%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
I'm interested in the problem, but can't follow the details of your approach. Could you provide a pseudo-code description of the algorithm?
– jwimberley
Nov 9 at 21:52
1
I'm assuming that the complexity you cite does not include the building of the trie (which would have to be at least O(N) times constant factor related to number of bits in each element of array), but reflects a scenario where you build a trie once and then repeatedly reuse for multiple queries Q, correct?
– jwimberley
Nov 9 at 22:07
Third and last comment for now: Does "if the current node of trie has index in range [L,R]" mean that each node in the trie includes a table of all (L,R) pairs for which there is an entry L<=idx<=R in the current node or any of its descendants?
– jwimberley
Nov 9 at 22:09
You keeping all the indexes of array in trie node, right? doen't it will require lots of memoty?
– nightfury1204
Nov 10 at 6:45