repeated element in Array

Question

I have an array of N elements and contain 1 to (N-1) integers-a sequence of integers starting from 1 to the max number N-1-, meaning that there is only one number is repeated, and I want to write an algorithm that return this repeated element, I have found a solution but it only could work if the array is sorted, which is may not be the case. ?

int i=0;
while(i<A[i])
{
i++
}
int rep = A[i];

Are you allowed to use an auxiliary map? Do you have any information about the contents of the array? — Mureinik
– Mureinik, Commented Oct 14, 2014 at 18:52
Can you attempt to insert the number into a HashSet? Whenever it already exists in the Set it would be duplicate and because it can be accessed directly it would be O(N) — Grice
– Grice, Commented Oct 14, 2014 at 18:55
@JGrice i do not think that using a HashSet would be O(N). if i recall correctly inserting is O(log(n)), so that you end up in O(n log(n)) — vlad_tepesch
– vlad_tepesch, Commented Oct 14, 2014 at 18:58
In worst case HashSet will give you O(N^2), it cannot be used as good theoretical solution — ursa
– ursa, Commented Oct 14, 2014 at 18:59
@ursa Did not know that worst case was O(n^2). What situation would cause this? Having to rehash the entire set when expanding size of it? — Grice
– Grice, Commented Oct 14, 2014 at 19:03

vlad_tepesch · Accepted Answer · 2014-10-14 19:18:29Z

1

I do not know why RC removed his comment but his idea was good.

With the knowledge of N you easy can calculate that the sum of [1:N-1]. then sum up all elementes in your array and subtract the above sum and you have your number.

This comes at the cost of O(n) and is not beatable.

However this only works with the preconditions you mentioned.

A more generic approach would be to sort the array and then simply walk through it. This would be O(n log(n)) and still better than your O(n²).

I you know the maximum number you may create a lookup table and init it with all zeros, walk through the array and check for one and mark the entries with one. The complexity is also just O(n) but at the expense of memory.

if the value range is unknown a simiar approach can be used but instead of using a lookup table a hashset canbe used.

edited Oct 14, 2014 at 19:18

answered Oct 14, 2014 at 18:57

vlad_tepesch

7,0272 gold badges46 silver badges89 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ursa Over a year ago

it would not work. e.g. N = 3, seq1 = 1, 1, 3 vs seq2 = 2, 2, 1.

vlad_tepesch Over a year ago

@ursa please reread the question. if N=3 then the array only contains 1 and 2 and on of them twice. (i changed the [1:N] to [1:N-1] since it was misundersoodable

ursa · Accepted Answer · 2014-10-14 18:57:40Z

0

Linear search will help you with complexity O(n):

final int n = ...;
final int a[] = createInput(n); // Expect each a[i] < n && a[i] >= 0
final int b[] = new int[n];

for (int i = 0; i < n; i++)
    b[i]++;

for (int i = 0; i < n; i++)
   if (b[i] >= 2)
      return a[i];

throw new IllegalArgumentException("No duplicates found");

answered Oct 14, 2014 at 18:57

ursa

4,7011 gold badge29 silver badges39 bronze badges

2 Comments

sage88 Over a year ago

This is a working O(n) solution, but if one of the numbers in the array was enormous your have to allocate a huge amount of memory, even if there were only a few numbers in the original array.

ursa Over a year ago

yes, but with condition "contain 1-(N-1) integers" its not the case. I understand that all values are between 1 and (N-1). is it your case, AbeerM93?

Ivaylo Strandjev · Accepted Answer · 2014-10-14 19:14:33Z

0

A possible solution is to sum all elements in the array and then to compute the sym of the integers up to N-1. After that subtract the two values and voila - you found your number. This is the solution proposed by vlad_tepesch and it is good, but has a drawback - you may overflow the integer type. To avoid this you can use 64 bit integer.

However I want to propose a slight modification - compute the xor sum of the integers up to N-1(that is compute 1^2^3^...(N-1)) and compute the xor sum of your array(i.e. a₀^a₁^...a_N-1). After that xor the two values and the result will be the repeated element.

edited Oct 14, 2014 at 19:14

answered Oct 14, 2014 at 19:07

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

2 Comments

vlad_tepesch Over a year ago

the sum approach initially was from RC.

rici Over a year ago

Alternatively, do the sum modulo N if N is odd, or modulo N-1 if N is even. The extra number is the result unless the result is 0 in which case the extra number is N-1.

Collectives™ on Stack Overflow

repeated element in Array

3 Answers 3

2 Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related