Validating that an array has no duplicated values

Question

Suppose we have an array in the size of n, with values range from 0 to n-1. A function that validates that there are no duplications of values is needed, without using another array.

Prototype: bool UniqueValues(unsigned arr[], size_t n);

This is an algorithm question for job interviews, please don't suggest using built-in std functions.

I don't see how this question is too localized, it is an algorithm question, and it encourage thinking and sovling problems. I'm surprised it's been voted to close. — StackHeapCollision, Dec 28 '12 at 10:55
You haven't shown your work. Questions asking for an implementation of an algorithm from the ground up are not in-scope at SO. That's not to say it isn't a good or interesting question, but not every good or interesting question has a home on SO. — John Dibling, Dec 28 '12 at 15:13
This question presents a question from a job interview, what else is there to be shown? They don't give you extra information in job interviews. And I'm pretty sure SO has a lot of job interviews questions posted, and are acceptable. Such as this one: http://stackoverflow.com/questions/3931464/another-algorithm-job-interview Not much of information was specified there. — StackHeapCollision, Dec 28 '12 at 22:02

score 4 · Accepted Answer · answered Dec 27 '12 at 19:21

Traverse the array and for each element, swap arr[i] with arr in the index of arr[i]( e.g, if arr[1]=2, swap it with arr[2], so arr[2]=2). The indication whether the value is duplicated is that arr[ arr[i] ] == arr[i]. (found 2 somewhere when there is already 2 at arr[2]).

bool UniqueValues(unsigned arr[], size_t n)
{
    int val;
    for(size_t i=0;i<n;i++)
    {
        val = arr[i];
        if(val == arr[val] )  { if( val != i) return false; }  //  If the element is duplicated
        else {
            swap( arr[i], arr[val] );  //  Move the element to the index matching its value
            val = arr[i];
            if(val == arr[val] )  return false;  //  Another check for the swapped element
        }
    }
    return true;
}

score 1 · Answer 2 · answered Dec 27 '12 at 19:26

1

A quick test is to sum the numbers in the array, then sum the subscripts. If the two are not equal then there is likely to be a duplicate.

For a stronger statement sort the array. The values should line up with the subscripts.

answered Dec 27 '12 at 19:26

EvilTeach

28,120
21
85
141

array[0] = array[2] = 1; array[1] = array[3] = 2; – brian beuning Dec 27 '12 at 19:33
2

Think again. What if you have 0 1 1 4 4 5 6 7 8 9 – StackHeapCollision Dec 27 '12 at 19:33
@stack. Doesn't apply. If the two do sum to the same value there is no conclusion, hence the stronger statement. The quick test is a fast way to fail. – EvilTeach Dec 27 '12 at 22:49

score 1 · Answer 3 · answered Dec 27 '12 at 19:27

One solution would be (pseudo code)

loop from i = 0 while i is smaller than length of array {
  loop from j = i + 1 while j is smaller than length of array {
    if array at index i equals array at index j {
      duplicate found. terminate the algorithm
    }
  }
}

no duplicate found.

Validating that an array has no duplicated values

3 Answers3