# Find duplicates in O(n) time and O(1) extra space | Set 1

Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

For example, let n be 7 and array be {1, 2, 3, 1, 3, 6, 6}, the answer should be 1, 3 and 6.

This problem is an extended version of the following problem.

Find the two repeating elements in a given array

Method 1 and Method 2 of the above link are not applicable as the question says O(n) time complexity and O(1) constant space. Also, Method 3 and Method 4 cannot be applied here because there can be more than 2 repeating elements in this problem. Method 5 can be extended to work for this problem. Below is the solution that is similar to the Method 5.

Algorithm:

```traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
this   element (ith element of list) is a repetition
}```

Implementation:

br>

## C++

 `// C++ code to find ` `// duplicates in O(n) time ` `#include ` `using` `namespace` `std; ` ` `  `// Function to print duplicates ` `void` `printRepeating(``int` `arr[], ``int` `size) ` `{ ` `int` `i; ` `cout << ``"The repeating elements are:"` `<< endl; ` `for` `(i = 0; i < size; i++) ` `{ ` `    ``if` `(arr[``abs``(arr[i])] >= 0) ` `    ``arr[``abs``(arr[i])] = -arr[``abs``(arr[i])]; ` `    ``else` `    ``cout << ``abs``(arr[i]) << ``" "``; ` `} ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 2, 3, 1, 3, 6, 6}; ` `    ``int` `arr_size = ``sizeof``(arr)/``sizeof``(arr); ` `    ``printRepeating(arr, arr_size); ` `    ``return` `0; ` `} ` ` `  `// This code is contributed  ` `// by Akanksha Rai `

## C

 `// C code to find ` `// duplicates in O(n) time ` `#include ` `#include ` ` `  `// Function to print duplicates ` `void` `printRepeating(``int` `arr[], ``int` `size) ` `{ ` `  ``int` `i; ` `  ``printf``(````"The repeating elements are: "````); ` `  ``for` `(i = 0; i < size; i++) ` `  ``{ ` `    ``if` `(arr[``abs``(arr[i])] >= 0) ` `      ``arr[``abs``(arr[i])] = -arr[``abs``(arr[i])]; ` `    ``else` `      ``printf``(``" %d "``, ``abs``(arr[i])); ` `  ``} ` `} ` ` `  `int` `main() ` `{ ` `  ``int` `arr[] = {1, 2, 3, 1, 3, 6, 6}; ` `  ``int` `arr_size = ``sizeof``(arr)/``sizeof``(arr); ` `  ``printRepeating(arr, arr_size); ` `  ``getchar``(); ` `  ``return` `0; ` `} `

## Java

 `// Java code to find ` `// duplicates in O(n) time ` ` `  `class` `FindDuplicate ` `{ ` ` ``// Function to print duplicates ` `    ``void` `printRepeating(``int` `arr[], ``int` `size) ` `    ``{ ` `        ``int` `i;   ` `        ``System.out.println(``"The repeating elements are : "``); ` `    `  `        ``for` `(i = ``0``; i < size; i++) ` `        ``{ ` `            ``if` `(arr[Math.abs(arr[i])] >= ``0``) ` `                ``arr[Math.abs(arr[i])] = -arr[Math.abs(arr[i])]; ` `            ``else` `                ``System.out.print(Math.abs(arr[i]) + ``" "``); ` `        ``}          ` `    ``}  ` ` `  `    ``// Driver program  ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``FindDuplicate duplicate = ``new` `FindDuplicate(); ` `        ``int` `arr[] = {``1``, ``2``, ``3``, ``1``, ``3``, ``6``, ``6``}; ` `        ``int` `arr_size = arr.length; ` ` `  `        ``duplicate.printRepeating(arr, arr_size); ` `    ``} ` `} ` ` `  `// This code has been contributed by Mayank Jaiswal `

## Python3

 `# Python3 code to find ` `# duplicates in O(n) time ` ` `  `# Function to print duplicates ` `def` `printRepeating(arr, size): ` `     `  `    ``print``(``"The repeating elements are: "``) ` `     `  `    ``for` `i ``in` `range``(``0``, size): ` `         `  `        ``if` `arr[``abs``(arr[i])] >``=` `0``: ` `            ``arr[``abs``(arr[i])] ``=` `-``arr[``abs``(arr[i])] ` `        ``else``: ` `            ``print` `(``abs``(arr[i]), end ``=` `" "``) ` `             `  `# Driver code ` `arr ``=` `[``1``, ``2``, ``3``, ``1``, ``3``, ``6``, ``6``] ` `arr_size ``=` `len``(arr) ` ` `  `printRepeating(arr, arr_size) ` ` `  `# This code is contributed by Shreyanshi Arun. `

## C#

 `// C# code to find ` `// duplicates in O(n) time ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``static` `void` `printRepeating(``int` `[]arr, ` `                            ``int` `size) ` `    ``{ ` `        ``int` `i;  ` `         `  `        ``Console.Write(``"The repeating"` `+  ` `                       ``" elements are : "``); ` `     `  `        ``for` `(i = 0; i < size; i++) ` `        ``{ ` `            ``if` `(arr[Math.Abs(arr[i])] >= 0) ` `                ``arr[Math.Abs(arr[i])] = ` `                    ``-arr[Math.Abs(arr[i])]; ` `            ``else` `                ``Console.Write(Math.Abs(arr[i]) + ``" "``); ` `        ``}          ` `    ``}  ` ` `  `    ``// Driver program  ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``int` `[]arr = {1, 2, 3, 1, 3, 6, 6}; ` `        ``int` `arr_size = arr.Length; ` ` `  `        ``printRepeating(arr, arr_size); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 `= 0) ` `            ``\$arr``[``abs``(``\$arr``[``\$i``])] = -``\$arr``[``abs``(``\$arr``[``\$i``])]; ` `        ``else` `            ``echo` `abs``(``\$arr``[``\$i``]) . ``" "``; ` `    ``} ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(1, 2, 3, 1, 3, 6, 6); ` `\$arr_size` `= ``count``(``\$arr``); ` `printRepeating(``\$arr``, ``\$arr_size``); ` ` `  `// This code is contributed by Sam007 ` `?> `

Output:

```The repeating elements are:
1  3  6```

Note: The above program doesn’t handle 0 case (If 0 is present in array). The program can be easily modified to handle that also. It is not handled to keep the code simple.

Time Complexity: O(n)
Auxiliary Space: O(1)

There is a problem in above approach. It prints the repeated number more than once. For example: {1, 6, 3, 1, 3, 6, 6} it will give output as : 1 3 6 6. In below set, another approach is discussed that prints repeating elements only once.

Duplicates in an array in O(n) and by using O(1) extra space | Set-2

Another O(n) & O(1) java code:

class Leet442
{
public static void main(String args [ ])
{
int numRay[] = {0,4,3,2,7,8,2,3,1};

for(int i = 0; i < numRay.length; i++) numRay[numRay[i]%10] = numRay[numRay[i]%10] + 10; System.out.println("The repeating elements are : "); for(int i = 0; i < numRay.length; i++) if(numRay[i] > 19)
System.out.println(i+” “);
}
}

OUTPUT:
The repeating elements are :
2
3

//This code contributed by glasshopper

Please write comments if you find the above codes/algorithms incorrect, or find better ways to solve the same problem.

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Amazon Paytm Paytm Amazon Arrays

code

load comments