Table of Contents

## 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; }

### Java Program for Find Duplicates in an Array in Most Efficient Way

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

## Complexity Analysis for Find Duplicates in an Array in Most Efficient Way

**Time Complexity **

**O(N) **where N is the number of elements present in the given array, Here we traverse the whole array and compute our answer.

**Space Complexity **

**O(1) **because we won’t use auxiliary space in the computation of results.