Find duplicates in an array in linear time
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?
arrays algorithm search duplicates
New contributor
add a comment |
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?
arrays algorithm search duplicates
New contributor
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 in1..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 withm = 1
and, for each element, ifm % mapped_elem == 0
then it is duplicate, otherwise dom *= 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? Imaginen=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
add a comment |
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?
arrays algorithm search duplicates
New contributor
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
New contributor
New contributor
edited Nov 13 at 3:54
New contributor
asked Nov 12 at 17:29
Anguium
42
42
New contributor
New contributor
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 in1..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 withm = 1
and, for each element, ifm % mapped_elem == 0
then it is duplicate, otherwise dom *= 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? Imaginen=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
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 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..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 withm = 1
and, for each element, ifm % mapped_elem == 0
then it is duplicate, otherwise dom *= 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? Imaginen=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
add a comment |
active
oldest
votes
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.
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.
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
yy9x2Pud
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 withm = 1
and, for each element, ifm % mapped_elem == 0
then it is duplicate, otherwise dom *= 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