Describe an $O(N)$ time algorithm for determining if there is an integer in a sequence $A$ and an integer in...
up vote
1
down vote
favorite
Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:
Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.
I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:
if(A[a] + B[b] < x) -> update index a to be a + 1
if(A[a] + B[b] > x) -> update index b to be b - 1
if(A[a] + B[b] = x) -> success
However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.
algorithms asymptotics
asked Jan 23 '16 at 6:13
Alex
2872620
add a comment |
up vote
1
down vote
favorite
Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:
Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.
I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:
if(A[a] + B[b] < x) -> update index a to be a + 1
if(A[a] + B[b] > x) -> update index b to be b - 1
if(A[a] + B[b] = x) -> success
However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.
algorithms asymptotics
asked Jan 23 '16 at 6:13
Alex
2872620
2
My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22
I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29
Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29
2
I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:
Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.
I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:
if(A[a] + B[b] < x) -> update index a to be a + 1
if(A[a] + B[b] > x) -> update index b to be b - 1
if(A[a] + B[b] = x) -> success
However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.
algorithms asymptotics
asked Jan 23 '16 at 6:13
Alex
2872620
Unfortunately I couldn't make the title for my question long and I didn't really know how to shorten it, so there are some added constraints:
Let $A$ and $B$ be two sequences of $n$ integers each, in the range $[1 ldots n^4]$. Given an integer $x$, describe an $O(n)$-time algorithm for determining if there is an integer $a$ in $A$ and an integer $b$ in $B$ such that $x = a + b$.
I don't really know how to solve this in $O(N)$ time. The first thing I could think of was sorting both sequences $A$ and $B$ (which would take $O(nlog n)$ and then having $a$ be the first integer in sequence $A$ and $b$ be the last integer for sequence $B$. I could then check:
if(A[a] + B[b] < x) -> update index a to be a + 1
if(A[a] + B[b] > x) -> update index b to be b - 1
if(A[a] + B[b] = x) -> success
However, this algorithm is not $O(N)$ time. So, I'm wondering what kind of hint or trick would need to be used in order to solve this problem.
algorithms asymptotics
algorithms asymptotics
asked Jan 23 '16 at 6:13
Alex
2872620
asked Jan 23 '16 at 6:13
Alex
2872620
asked Jan 23 '16 at 6:13
Alex
2872620
asked Jan 23 '16 at 6:13
Alex
2872620
asked Jan 23 '16 at 6:13
Alex
2872620
2872620
2
My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22
I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29
Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29
2
I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08
add a comment |
2
My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22
I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29
Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29
2
I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08
2
2
My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22
My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22
I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29
I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29
Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29
Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29
2
2
I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08
I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08
add a comment |
2 Answers
2
active
oldest
votes
up vote
0
down vote
Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.
answered Jan 23 '16 at 6:35
Dan Simon
739611
1
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
add a comment |
up vote
0
down vote
Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.
A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.
Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2fmath.stackexchange.com%2fquestions%2f1623228%2fdescribe-an-on-time-algorithm-for-determining-if-there-is-an-integer-in-a-se%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.
answered Jan 23 '16 at 6:35
Dan Simon
739611
1
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
add a comment |
up vote
0
down vote
Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.
answered Jan 23 '16 at 6:35
Dan Simon
739611
1
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
add a comment |
up vote
0
down vote
up vote
0
down vote
Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.
answered Jan 23 '16 at 6:35
Dan Simon
739611
Allocate a hash map $H$. For each $a in A$, set $H[x - a]$ to 1. Then, for each $b in B$, if $H[b]$ is 1, you are done. Hash maps are $O(1)$ and worst case you traverse each list once, so the algorithm is $O(n)$.
answered Jan 23 '16 at 6:35
Dan Simon
739611
answered Jan 23 '16 at 6:35
Dan Simon
739611
answered Jan 23 '16 at 6:35
Dan Simon
739611
answered Jan 23 '16 at 6:35
Dan Simon
739611
739611
1
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
add a comment |
1
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
1
1
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
How can you guarantee only a constant number of collisions in each hash bucket?
– Dan Brumleve
Jan 23 '16 at 6:38
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Excellent question, I hadn't thought of that. I think at that point you'd have to do something clever that takes advantage of the $n^4$ range of values. For small enough $n$ (or assuming a computer with infinite memory), you could just use a $n^4$ sized array. Otherwise I suspect max number of collisions can be made constant using an appropriate hashing function based on $n$.
– Dan Simon
Jan 23 '16 at 6:51
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Also we are looking for worst case not average case. What if all the numbers end up in the same bucket?
– Dan Brumleve
Jan 23 '16 at 6:57
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
Yes, I think a radix-sort-like approach like you mention in the comments could work. You can do it with nested hash maps, but now that I think about it, I think it would be easier to just create a Trie structure out of the digits of all the $x - a$ and traverse it with each $b$. Both building the trie and traversing it for all $B$ are $O(n)$.
– Dan Simon
Jan 23 '16 at 7:39
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
I think we're to assume a model where arithmetic operations are constant. But there are $O(n cdot log{n})$ total digits, so we don't have enough time to inspect them all which would be required for the trie approach. I'm still not really sure about the radix sort idea.
– Dan Brumleve
Jan 23 '16 at 20:38
add a comment |
up vote
0
down vote
Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.
A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.
Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
add a comment |
up vote
0
down vote
Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.
A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.
Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
add a comment |
up vote
0
down vote
up vote
0
down vote
Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.
A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.
Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
Let's simplify the problem, like how Dan Simon does in his answer: subtract each element of $A$ from $x$ and call the resulting set $A'$. Now the original problem is equivalent to $A' cap B ne emptyset$, and also $vert A' cup B vert lt 2 cdot n$.
A straightforward way to present this problem is as a list of $2cdot n$ words of size $w = lceil 1 + 4 cdot log_2{n} rceil = O(log{n})$. But this means the radix sort idea I mentioned cannot work in $O(n)$ since radix sort is $O(n cdot w) = O(n cdot log{n})$. Nor can any method that operates on every bit or digit of the input numbers since there are $O(n cdot log{n})$ of them.
Maybe it is possible somehow without looking at every digit, given that we can perform arithmetic operations on entire words in constant time, so this is not a complete answer. But I cannot figure out how it might be done.
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
edited Jan 26 '16 at 5:42
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
answered Jan 26 '16 at 4:25
Dan Brumleve
12k53787
12k53787
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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%2fmath.stackexchange.com%2fquestions%2f1623228%2fdescribe-an-on-time-algorithm-for-determining-if-there-is-an-integer-in-a-se%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
2
My guess is that the solution would involve concatenating representations of the integers. The upper limit of $n^4$ is probably important. Also, in time $O(n)$ you can find the min and max of each sequence. Just throwing ideas out. Remember that free ideas are sometimes worth it. Say goodnight, Gracie.
– marty cohen
Jan 23 '16 at 6:22
I think you can use radix sort since the range is bounded?
– Dan Brumleve
Jan 23 '16 at 6:29
Are $n$ and $N$ the same thing? I assumed so in my answer because you have used them interchangably but if $N$ means the total input size and $n$ means the length of the list then there is an easy answer.
– Dan Brumleve
Jan 26 '16 at 4:29
2
I suspect $A$ and $B$ are sorted when they are given to you and your approach is the desired answer.
– Ross Millikan
Jan 26 '16 at 5:08