Find duplicates in an array in linear time
Problem: You are given an array of n+1 integers from range 1..n. At least one number has duplicate. All array values can be same. Print all duplicates in linear time and constant space. Array can't be modified.
The obvious solution would be to create a bit array with default value false, set 1 in bitarray[array[i]] for each element, then check if it's already 1. That requires additional space, so no good. My another thought: reorder the array by hash and check if a current element and the element array[hash % n] are equal. This is also no good since we can't modify the original array. Now I think that it looks like an impossible task. Is there even a solution to this?
arrays algorithm search duplicates
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
add a comment |
Problem: You are given an array of n+1 integers from range 1..n. At least one number has duplicate. All array values can be same. Print all duplicates in linear time and constant space. Array can't be modified.
The obvious solution would be to create a bit array with default value false, set 1 in bitarray[array[i]] for each element, then check if it's already 1. That requires additional space, so no good. My another thought: reorder the array by hash and check if a current element and the element array[hash % n] are equal. This is also no good since we can't modify the original array. Now I think that it looks like an impossible task. Is there even a solution to this?
arrays algorithm search duplicates
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
1
This may be a duplicate of stackoverflow.com/questions/5766936/…. Even if it isn't that Q, and others here on SO, provide much to consider.
– High Performance Mark
Nov 12 '18 at 17:35
Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in1..nto another number such that all the mappings are coprime to each other. If you can get that, then you could just have start withm = 1and, for each element, ifm % mapped_elem == 0then it is duplicate, otherwise dom *= mapped_elem. However I don't know if it's possible to do such mapping (quickly).
– jdehesa
Nov 12 '18 at 18:17
4
Is this even possible in the general case? Imaginen=999999and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input?
– Jim Mischel
Nov 12 '18 at 18:29
add a comment |
Problem: You are given an array of n+1 integers from range 1..n. At least one number has duplicate. All array values can be same. Print all duplicates in linear time and constant space. Array can't be modified.
The obvious solution would be to create a bit array with default value false, set 1 in bitarray[array[i]] for each element, then check if it's already 1. That requires additional space, so no good. My another thought: reorder the array by hash and check if a current element and the element array[hash % n] are equal. This is also no good since we can't modify the original array. Now I think that it looks like an impossible task. Is there even a solution to this?
arrays algorithm search duplicates
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
Problem: You are given an array of n+1 integers from range 1..n. At least one number has duplicate. All array values can be same. Print all duplicates in linear time and constant space. Array can't be modified.
The obvious solution would be to create a bit array with default value false, set 1 in bitarray[array[i]] for each element, then check if it's already 1. That requires additional space, so no good. My another thought: reorder the array by hash and check if a current element and the element array[hash % n] are equal. This is also no good since we can't modify the original array. Now I think that it looks like an impossible task. Is there even a solution to this?
arrays algorithm search duplicates
arrays algorithm search duplicates
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
edited Nov 13 '18 at 3:54
Anguium
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
asked Nov 12 '18 at 17:29
AnguiumAnguium
2114
2114
1
This may be a duplicate of stackoverflow.com/questions/5766936/…. Even if it isn't that Q, and others here on SO, provide much to consider.
– High Performance Mark
Nov 12 '18 at 17:35
Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in1..nto another number such that all the mappings are coprime to each other. If you can get that, then you could just have start withm = 1and, for each element, ifm % mapped_elem == 0then it is duplicate, otherwise dom *= mapped_elem. However I don't know if it's possible to do such mapping (quickly).
– jdehesa
Nov 12 '18 at 18:17
4
Is this even possible in the general case? Imaginen=999999and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input?
– Jim Mischel
Nov 12 '18 at 18:29
add a comment |
1
This may be a duplicate of stackoverflow.com/questions/5766936/…. Even if it isn't that Q, and others here on SO, provide much to consider.
– High Performance Mark
Nov 12 '18 at 17:35
Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in1..nto another number such that all the mappings are coprime to each other. If you can get that, then you could just have start withm = 1and, for each element, ifm % mapped_elem == 0then it is duplicate, otherwise dom *= mapped_elem. However I don't know if it's possible to do such mapping (quickly).
– jdehesa
Nov 12 '18 at 18:17
4
Is this even possible in the general case? Imaginen=999999and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input?
– Jim Mischel
Nov 12 '18 at 18:29
1
1
This may be a duplicate of stackoverflow.com/questions/5766936/…. Even if it isn't that Q, and others here on SO, provide much to consider.
– High Performance Mark
Nov 12 '18 at 17:35
This may be a duplicate of stackoverflow.com/questions/5766936/…. Even if it isn't that Q, and others here on SO, provide much to consider.
– High Performance Mark
Nov 12 '18 at 17:35
Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in
1..n to another number such that all the mappings are coprime to each other. If you can get that, then you could just have start with m = 1 and, for each element, if m % mapped_elem == 0 then it is duplicate, otherwise do m *= mapped_elem. However I don't know if it's possible to do such mapping (quickly).– jdehesa
Nov 12 '18 at 18:17
Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in
1..n to another number such that all the mappings are coprime to each other. If you can get that, then you could just have start with m = 1 and, for each element, if m % mapped_elem == 0 then it is duplicate, otherwise do m *= mapped_elem. However I don't know if it's possible to do such mapping (quickly).– jdehesa
Nov 12 '18 at 18:17
4
4
Is this even possible in the general case? Imagine
n=999999 and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input?– Jim Mischel
Nov 12 '18 at 18:29
Is this even possible in the general case? Imagine
n=999999 and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input?– Jim Mischel
Nov 12 '18 at 18:29
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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',
autoActivateHeartbeat: false,
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
},
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%2fstackoverflow.com%2fquestions%2f53267218%2ffind-duplicates-in-an-array-in-linear-time%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Stack Overflow!
- 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%2fstackoverflow.com%2fquestions%2f53267218%2ffind-duplicates-in-an-array-in-linear-time%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
1
This may be a duplicate of stackoverflow.com/questions/5766936/…. Even if it isn't that Q, and others here on SO, provide much to consider.
– High Performance Mark
Nov 12 '18 at 17:35
Not sure if this makes sense, but I'm thinking one possible algorithm would be to have some mapping for each number in
1..nto another number such that all the mappings are coprime to each other. If you can get that, then you could just have start withm = 1and, for each element, ifm % mapped_elem == 0then it is duplicate, otherwise dom *= mapped_elem. However I don't know if it's possible to do such mapping (quickly).– jdehesa
Nov 12 '18 at 18:17
4
Is this even possible in the general case? Imagine
n=999999and the array contains the numbers 1 through 1000, duplicated 1000 times each. If I can't modify the array or use additional space proportional to n, it doesn't seem likely that this can be done in linear time. Are you sure there are no other restrictions on the input?– Jim Mischel
Nov 12 '18 at 18:29