The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Find the duplicate elements in an array of size n where each element is in the range 0 to n-1.

Solution :-
Approach 1 :: Compare each element of the array with all other elements (using two loops) [ O(n2) solution ( not an efficient one) ]
Approach 2 :: Maintain a hash table. Set the hash value to 1 if we encounter the element for the first time. If we see it second time ( we check it by looking at the hash value ), print it [ efficient in terms of time O(n) but additional space is required ]
Approach 3 :: We will exploit the constraint "every element is in the range 0 to n-1".
Suppose we see an element 4 in the array. We will make arr[4] negative.
So while traversing the array, if we see a negative value, we will print the index of that value.
Considering our example, we will find arr[4] negative and so we will print 4.

#include<iostream>
#include<cmath>
using namespace std;

// find all the duplicate elements in an array of size
// 'n' where all elements are in the range 0 to n-1
// If an element 'k' is present in an array, we will
// make the value at index 'k' negative
// i.e if k = 4 then arr[k] = -arr[k]
void findDuplicates(int arr[],int size) {
   int i;
   int k;
   for (i=0;i<size;i++) {
      k = abs(arr[i]);
      if (arr[k] >= 0) {
         // k was not seen previously
         // mark k as seen
         arr[k] = -arr[k];
      }
      else {
         // arr[k] is negative
         // this implies 'k' was seen previously
         cout<<k<<" ";
      }
   }
}

// main
int main() {
   int arr[] = {3,5,1,6,5,7,3,6};
   int size = sizeof(arr)/sizeof(arr[0]);
   findDuplicates(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)