Home Arrays Write a program to check if there are any duplicated elements in an array? (Method 3)

# Write a program to check if there are any duplicated elements in an array? (Method 3)

0 comment

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

Another possible and better way to solve this problem based on a certain condition.

Let us assume that the array elements are positive numbers and also all the elements are in the range 0 to n-1. For each element A[i], go to the array element whose index is A[i]. That means we select A[A[i]] and mark it as a negative number -A[A[i]] (that means we negate the value at A[A[i]]). Continue this process until we encounter the element whose value is already negated. If one such element exists then we say duplicate elements exist in the given array. As an example, consider this array arr[] = {3, 2, 1, 2, 2, 3}

At the last step, we can observe that arr[abs[arr[3]] is already negative. That means we have encountered the same value again. The algorithm can be coded as:-

void checkDuplicates(int arr[], int size)
{
int i = 0;

for(i=0;i<size;i++)
{
if(arr[abs(arr[i])] < 0)
{
printf("Duplicates exist");
return;
}
else
//negate the value
arr[arr[i]] = -1 * arr[arr[i]];
}
printf("NO Duplicates found");
}


Time Complexity:- O(n), Since only one scan is required.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More