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

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++)
	{
		//check if already negative
		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.