Find duplicates in an array in linear time

Multi tool use
Multi tool use











up vote
0
down vote

favorite












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?










share|improve this question









New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 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 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 at 18:17






  • 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 at 18:29

















up vote
0
down vote

favorite












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?










share|improve this question









New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 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 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 at 18:17






  • 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 at 18:29















up vote
0
down vote

favorite









up vote
0
down vote

favorite











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?










share|improve this question









New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











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






share|improve this question









New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited Nov 13 at 3:54





















New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Nov 12 at 17:29









Anguium

42




42




New contributor




Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Anguium is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 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 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 at 18:17






  • 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 at 18:29
















  • 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 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 at 18:17






  • 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 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 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 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 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 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 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 at 18:29



















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',
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
});


}
});






Anguium is a new contributor. Be nice, and check out our Code of Conduct.










 

draft saved


draft discarded


















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






























active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes








Anguium is a new contributor. Be nice, and check out our Code of Conduct.










 

draft saved


draft discarded


















Anguium is a new contributor. Be nice, and check out our Code of Conduct.













Anguium is a new contributor. Be nice, and check out our Code of Conduct.












Anguium is a new contributor. Be nice, and check out our Code of Conduct.















 


draft saved


draft discarded














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





















































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







yy9x2Pud
hL0 3L6vpUId3ZJPm5vPrxYpjaOB

Popular posts from this blog

mysqli_query(): Empty query in /home/lucindabrummitt/public_html/blog/wp-includes/wp-db.php on line 1924

How to change which sound is reproduced for terminal bell?

Can I use Tabulator js library in my java Spring + Thymeleaf project?