*895*

Question:Given an array of n numbers, give an algorithm for checking whether there are any duplicated elements in the array or not?

Input:4, 8, 15, 16, 23, 42

Output:NO

Input:4, 8, 4, 15, 23, 42

Output:YES

This is one of the simplest problems. One obvious solution to this is, exhaustively searching for duplicated elements in the array. That means, for each input element check whether there is any element with the same value. This we can solve by using two simple *for* loops. The code can be written as:-

//checks duplicate in an array arr[] of size int checkDuplicatesBruteForce(int arr[], int size) { //the flag to return int duplicate_exist = 0; int i,j; for(i = 0; i<size; i++) { for(j = i+1; j<size; j++) { if(arr[i] == arr[j]) { //we have found a duplicate, change the flag //and break the loop. No need to check further. duplicate_exist = 1; break; } } } return duplicate_exist; }

Time Complexity:- O(n^{2})

Space Complexity:- O(1)

Click here to find a better approach of solving the above problem.