Check if there are any repeated elements in an array recursively

Question

I have to find recursively if there is any repeated element in an integer array v. The method must have the following signature:

boolean hasRepeatedElements(int[] v) 

I can't see any way of doing that recursively without having to define another method or at least another overload to this method (one that takes for example the element to go after or something). At first I thought about checking for the current v if there is some element equal to the first element, then creating a new array with L-1 elements etc but that seems rather inefficient. Is it the only way?

Am I missing here something?

Answer 1

Iterating would be quicker. Or using container class. Your way will work, but won't be very efficient. If this was C, instead of copying you could just call hadRepeatedElements(v + 1)

Answer 2

If it must be recursive with that signature...

You could also sort the array and compare the first two elements. Then make a recursive call with elements [1..n].

Answer 3

I agree that recursion is not terribly necessary here, but it can be used. Do you know quick-sort algorithm? Same divide-and-conquer approach can be taken here.

boolean hasRepeatedElements(list v) 
    if v.length <= 1 return false;
    List less, greater;
    x = v[0];
    for each y in v, except v[0]
        if y == x
            return true;
        else if y < x
            less.add(y);
        else if y > x
            greater.add(y);
    end;
    return hasRepeatedElements(less) || hasRepeatedElements(greater);
end;

You can also add randomization to make algorithm statistically O(n*log(n)).

http://en.wikipedia.org/wiki/Quicksort

Answer 4

I'm sure someone out there smarter than me could do this more efficiently, but at least it works.

bool hasRepeatedElements(int[] v)
        {
            if (v.Length > 1)
            {
                int[] subArray = new int[v.Length - 1];
                for (int i = 1; i < v.Length; i++)
                {
                    if (v[0] == v[i])
                        return true;
                    else
                        subArray[i - 1] = v[i];
                }
                return hasRepeatedElements(subArray);
            }

            return false;
        }

Answer 5

You can sort and compare at the same time, since that's effectively what a sorting algorithm would be doing. If your sorting algorithm is recursive you win :)

boolean hasRepeatedElements(int[] v) {
  if (v.length <= 1) return false;
  boolean switched = false;
  int[] sub = new int[v.length];
  for (int i = 0; i < v.length; i++)
    sub[i] = v[i];
  for (int i = 0; i < sub.length - 1; i++) {
    if (sub[i] > sub[i + 1]) {
      switched = true;
      int temp = sub[i];
      sub[i] = sub[i + 1];
      sub[i + 1] = temp;
    } 
    else if (sub[i] == sub[i + 1]) return true;
  }
  if (!switched) return false; //We have not sorted the array and found zero dups

  return hasRepeatedElements(sub); //The recursive bit

}

If you think this looks hurried it is, I have a flight to catch. The basic principal is there, someone here could almost certainly refine the code :)

Hope that helps.

Answer 6

If you do not like sorting, then this solution solves it without sorting. You should be able to make it much more efficient.

boolean hasRepeatedElements(int[] v) 
{
    if ( v . length <= 1 )
    {
        return ( false ) ;
    }
    int k = RANDOM . nextInt ( v . length ) ;
    int leftLength = v . length / 2 ;
    int [ ] left = new int [ leftLength ] ;
    int rightLength = v . length - l ;
    int [ ] rightLength = new int [ rightLength ] ;
    int i , l , r ;
    for ( i = 0 , l = 0 , r = 0 ; i < v . length ; i ++ )
    {
        if ( ( v [ i ] < v [ k ] ) & ( l < leftLength ) )
        {
            left [ l ] = v [ i ] ;
            l ++ ;
        }
        else if ( ( v [ i ] >= v [ k ] ) & ( r < rightLength ) )
        {
            right [ r ] = v [ i ] ;
            r ++ ;
        }
        else
        {
            return ( hasRepeatedElements ( v ) ) ;
        }
    }
    if ( hasRepeatedElements ( left ) ) { return ( true ) ; }
    if ( hasRepeatedElements ( right ) ) { return ( true ) ; }
    return ( false ) ;
}

This solution is not very efficient, but it uses recursion and it follows the method signature exactly.

static java . util . Random RANDOM = new java . util . Random ( ) ;

boolean hasRepeatedElements(int[] v) 
{
     int s = Random . nextInt ( v . length ) ;
     int t = Random . nextInt ( v . length ) ;
     int temp = v[s] ;
     v[s] = v[t] ;
     v[t] = temp ;
     for ( int i = 0 ; i < v . length - 1 ; i ++ )
     {
          if ( v[i]==v[i+1] ) { return true ; }
          else if ( v[i]>v[i+1] { return hasRepeatedElements ( v ) ; }
     }
     return false ;
}