Find Duplicates in an Array in Most Efficient Way

Problem Statement

Display all the elements which are duplicates in the most efficient way in O(n) and O(1) space. Given an array of size n which contains numbers from range 0 to n-1, these numbers can occur any number of times. Find duplicates in an array in the most efficient way. That is if the number has already occurred in the array, then the number is duplicate.

Example

Input

23

1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0

Output

4 1 0 2 4 4 2 4 6 1 0 0 0

Approach for Find Duplicates in an Array in Most Efficient Way

Now we understand the problem understand. So, without taking much time we directly move to the algorithm used for the implementation of the problem.

Algorithm

1.    Take a separate variable for handling the repetition of zero.
2.    Next, traverse the array.
3.    If the element is zero increment count of zero. If the count is greater than 1 then display it as it got duplicated.
4.    If it is other than zero, then go to the index of the array pointed by the absolute value of the element you are standing i.e. arr[abs(arr[i])] and if it is positive then make it negative implying that the element which is the index i has occurred once.
5.    If we get a duplicate then we will see that arr[abs(arr[i])] is already of opposite sign and we can simply print it.

Implementation

C++ Program for Find Duplicates in an Array in Most Efficient Way

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;//size of the array
    cin>>N;
    int arr[N];
    for(int i=0;i<N;i++)
    {
      cin>>arr[i];
    }
    int zero = 0; //separate case for zero
    for(int i = 0; i < N; i++)
    {
    if(arr[i] == 0)
      {
        if(zero > 0)
          cout << 0 << " ";
        
        zero++;
      }
      
    else if(arr[abs(arr[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
    arr[abs(arr[i])] = - arr[abs(arr[i])];
    
    else    //if we have duplicates then we will encounter a location whose value is negative
     cout << abs(arr[i]) <<" ";
   }
   return 0;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            return -1*x;
        }
        else
        {
            return x;
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int zero = 0; //separate case for zero
        for(int i = 0; i < n; i++)
        {
        if(a[i] == 0)
          {
            if(zero > 0)
              System.out.print(0+" ");
            zero++;
          }
        else if(a[abs(a[i])] >= 0)  // we take the element's value as the index and change the sign of the element at that position
        a[abs(a[i])] = - a[abs(a[i])];
        else    //if we have duplicates then we will encounter a location whose value is negative
         System.out.print(abs(a[i])+" ");
       }
    }
}

23
1 5 4 2 8 4 1 0 0 2 4 9 4 2 4 6 6 7 3 1 0 0 0

4 1 0 2 4 4 2 4 6 1 0 0 0