Monday, February 20, 2012

finding duplicate entry in an array.


/**
---------------------------------------------------------------------------
problem : 
----------
- find first duplicate value in the given array without modifying the array.
---------------------------------------------------------------------------
input : 
----------
- int *a : array of integers
- int l : number of elements in a
- int m : loose upper bound for value of an element of array a.  
        : 0 <= value_of_element_of_a < m
- relation between l and m : l > m
---------------------------------------------------------------------------
output : 
----------
- first duplicate value occuring in the array.
---------------------------------------------------------------------------
constraints : 
------------- 
- space requirement should be O(1)
- after the function returns the array should be same as original.
---------------------------------------------------------------------------
/**/

//-------------------------------------------------------------------------
int find_firstduplicate(int *a, int l, int m)
{
 int original = 0;
 int index = 0;
 int is_index_already_used = 0;
 const int adjustment_for_zero_value = 1;
 int duplicate = -1;

 for(index = 0; index <= m; ++index)
 {
  is_index_already_used = 0;
  original = a[index];

  if(a[index] < 0)
  {
   //means there is already an element with value = index
   is_index_already_used = 1;

   //reversing the step of procedure to handle zero value
   a[index] += adjustment_for_zero_value;

   //original value of the element
   original = abs(a[index]);
  }
  
  if(a[original] >= 0)
  {
   //negating
   a[original] = (- a[original]);
   
   //substracting 1, to handle zero value, since (minus ZERO) = (ZERO) 
   a[original] = a[original] - adjustment_for_zero_value;

   //restoring the fact that index is used.
   a[index] -= is_index_already_used;   
  }
  else
  {
   //duplicate found.
   duplicate = original;
   break;   
  }
 }

 //readjusting the values of array so that they resemble the original.
 for(index = 0; index <= m; ++index)
 {
  if(a[index] < 0)
  {   
   a[index] += adjustment_for_zero_value;
   a[index] = - a[index];
  }
 } 

 return duplicate;
}
//-------------------------------------------------------------------------

/**
---------------------------------------------------------------------------
solution :
- hint : use the value of element as an index 'i' and negate the value at  
index i.
- complexity : O(m) 
---------------------------------------------------------------------------
/**/

void main()
{
 int m = 5;
 int a[] = {1, 0, 3, 0, 4, 5};
 int l = sizeof(a) / sizeof(a[0]);
 int duplicate = find_firstduplicate(a, l, m);
 if(duplicate != -1)
 {
  cout << "first duplicate = " << duplicate << endl;
 }
 else
 {
  cout << "duplicate does not exist." << endl;
 }
 getch();
}

/**
output :
--------
first duplicate = 0
/**/