Find duplicates in constant array with elements 0 to N-1 in O(1) space
Given a constant array of n elements which contains elements from 1 to n-1, with any of these numbers appearing any number of times. Find any one of these repeating numbers in O(n) and using only constant memory space.
Examples:
Input : arr[] = {1, 2, 3, 4, 5, 6, 3} Output : 3
As the given array is constant methods given in below articles will not work.
- We are taking two variables i & j starting from 0
- We will run loop until i reached last elem or found repeated elem
- We will pre-increment the j value so that we can compare elem with next elem
- If we don’t find elem, we will increase i as j will be pointing last elem and then reposition j with
Implementation:
C++
#include <iostream> using namespace std; // function to find one duplicate int findduplicate( int a[], int n) { int i = 0, j = 0; while (i < n) { if (a[i] == a[++j]) return a[j]; if (j == n - 1) { i++; j = i; } } return -1; } int main() { int arr[] = { 1, 2, 4, 3, 4, 5, 6, 3 }; int n = sizeof (arr) / sizeof (arr[0]); cout << findduplicate(arr, n) << endl; return 0; } // This code is contributed by akashish__ |
Java
// Java program to find a duplicate // element in an array with values in // range from 0 to n-1. import java.io.*; import java.util.*; public class GFG { // function to find one duplicate static int findduplicate( int []a, int n) { int i= 0 ,j= 0 ; while (i<n){ if (a[i]==a[++j]) return a[j]; if (j==n- 1 ) { i++; j=i; } } return - 1 ; } public static void main(String args[]) { int []arr = { 1 , 2 , 4 , 3 , 4 , 5 , 6 , 3 }; int n = arr.length; System.out.print(findduplicate(arr, n)); } } // This code is contributed by // Love Raj |
Java
// Java program to find a duplicate // element in an array with values in // range from 0 to n-1. import java.io.*; import java.util.*; public class GFG { // function to find one duplicate static int findduplicate( int []arr, int n) { // return -1 because in these cases // there can not be any repeated element if (n <= 1 ) return - 1 ; // initialize fast and slow int slow = arr[ 0 ]; int fast = arr[arr[ 0 ]]; // loop to enter in the cycle while (fast != slow) { // move one step for slow slow = arr[slow]; // move two step for fast fast = arr[arr[fast]]; } // loop to find entry // point of the cycle fast = 0 ; while (slow != fast) { slow = arr[slow]; fast = arr[fast]; } return slow; } // Driver Code public static void main(String args[]) { int []arr = { 1 , 2 , 3 , 4 , 5 , 6 , 3 }; int n = arr.length; System.out.print(findduplicate(arr, n)); } } // This code is contributed by // Manish Shaw (manishshaw1) |
Python 3
# Python 3 program to find a duplicate # element in an array with values in # range from 0 to n-1. # function to find one duplicate def findduplicate(arr, n): # return -1 because in these cases # there can not be any repeated element if (n < = 1 ): return - 1 # initialize fast and slow slow = arr[ 0 ] fast = arr[arr[ 0 ]] # loop to enter in the cycle while (fast ! = slow) : # move one step for slow slow = arr[slow] # move two step for fast fast = arr[arr[fast]] # loop to find entry point of the cycle fast = 0 while (slow ! = fast): slow = arr[slow] fast = arr[fast] return slow # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 3 ] n = len (arr) print (findduplicate(arr, n)) # This code is contributed by ita_c |
C#
// C# program to find a duplicate // element in an array with values in // range from 0 to n-1. using System; using System.Collections.Generic; class GFG { // function to find one duplicate static int findduplicate( int []arr, int n) { // return -1 because in these cases // there can not be any repeated element if (n <= 1) return -1; // initialize fast and slow int slow = arr[0]; int fast = arr[arr[0]]; // loop to enter in the cycle while (fast != slow) { // move one step for slow slow = arr[slow]; // move two step for fast fast = arr[arr[fast]]; } // loop to find entry // point of the cycle fast = 0; while (slow != fast) { slow = arr[slow]; fast = arr[fast]; } return slow; } // Driver Code public static void Main() { int []arr = {1, 2, 3, 4, 5, 6, 3}; int n = arr.Length; Console.Write(findduplicate(arr, n)); } } // This code is contributed by // Manish Shaw (manishshaw1) |
PHP
<?php // PHP program to find a duplicate // element in an array with values in // range from 0 to n-1. // function to find one duplicate function findduplicate( $arr , $n ) { // return -1 because in these cases // there can not be any repeated element if ( $n <= 1) return -1; // initialize fast and slow $slow = $arr [0]; $fast = $arr [ $arr [0]]; // loop to enter in the cycle while ( $fast != $slow ) { // move one step for slow $slow = $arr [ $slow ]; // move two step for fast $fast = $arr [ $arr [ $fast ]]; } // loop to find entry point of the cycle $fast = 0; while ( $slow != $fast ) { $slow = $arr [ $slow ]; $fast = $arr [ $fast ]; } return $slow ; } // Driver Code $arr = array ( 1, 2, 3, 4, 5, 6, 3 ); $n = sizeof( $arr ); echo findduplicate( $arr , $n ); // This code is contributed by Tushil ?> |
Javascript
<script> // Javascript program to find a duplicate // element in an array with values in // range from 0 to n-1. // function to find one duplicate function findduplicate(arr, n) { // return -1 because in these cases // there can not be any repeated element if (n <= 1) return -1; // initialize fast and slow let slow = arr[0]; let fast = arr[arr[0]]; // loop to enter in the cycle while (fast != slow) { // move one step for slow slow = arr[slow]; // move two step for fast fast = arr[arr[fast]]; } // loop to find entry // point of the cycle fast = 0; while (slow != fast) { slow = arr[slow]; fast = arr[fast]; } return slow; } let arr = [1, 2, 3, 4, 5, 6, 3]; let n = arr.length; document.write(findduplicate(arr, n)); </script> |
Javascript
// function to find one duplicate function findduplicate( a, n) { let i = 0, j = 0; while (i < n) { if (a[i] == a[++j]) return a[j]; if (j == n - 1) { i++; j = i; } } return -1; } let arr = [ 1, 2, 4, 3, 4, 5, 6, 3 ]; let n = arr.length; console.log(findduplicate(arr, n)); // This code is contributed by akashish__ |
Output
4
Complexity Analysis:
- Time Complexity: O(n*n)
- Auxiliary Space: O(1)
Efficient Approach:
We will use the concept that all elements here are between 1 and n-1.
So we will perform these steps to find the Duplicate element
- Consider a pointer ‘p’ which is currently at index 0.
- Run a while loop until the pointer p reaches the value n.
- if the value of a[p] is -1 then increment the pointer by 1 and skip the iteration
- Else,go to the position of the element to which the current pointer is pointing i.e. at index a[p].
- Now if the value at index a[p] i.e. a[a[p]] is -1 then break the loop as the element a[p] is the duplicate one.
- Otherwise store the value of a[a[p]] in a[p] i.e. a[p]=a[a[p]] and put -1 in a[a[p]] i.e. a[a[p]]=-1.
Code:
C++
#include <iostream> using namespace std; void find_duplicate( int a[], int n) { int p = 0; while (p != n) { if (a[p] == -1) { p++; } else { if (a[a[p] - 1] == -1) { cout << a[p] << endl; break ; } else { a[p] = a[a[p] - 1]; a[a[p] - 1] = -1; } } } } int main() { int a[] = { 1, 2, 4, 3, 4, 5, 6, 3 }; int n = sizeof (a) / sizeof (a[0]); find_duplicate(a, n); return 0; } // This Code is Contributed by Abhishek Purohit |
Java
// Java Program for the above approach import java.io.*; class GFG { static void find_duplicate( int a[], int n) { int p = 0 ; while (p != n) { if (a[p] == - 1 ) { p++; } else { if (a[a[p] - 1 ] == - 1 ) { System.out.println(a[p]); break ; } else { a[p] = a[a[p] - 1 ]; a[a[p] - 1 ] = - 1 ; } } } } public static void main(String[] args) { int [] a = { 1 , 2 , 4 , 3 , 4 , 5 , 6 , 3 }; int n = a.length; find_duplicate(a, n); } } // This Code is Contributed by lokesh (lokeshmvs21). |
Python3
class GFG : @staticmethod def find_duplicate( a, n) : p = 0 while (p ! = n) : if (a[p] = = - 1 ) : p + = 1 else : if (a[a[p] - 1 ] = = - 1 ) : print (a[p]) break else : a[p] = a[a[p] - 1 ] a[a[p] - 1 ] = - 1 @staticmethod def main( args) : a = [ 1 , 2 , 4 , 3 , 4 , 5 , 6 , 3 ] n = len (a) GFG.find_duplicate(a, n) if __name__ = = "__main__" : GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// Include namespace system using System; public class GFG { public static void find_duplicate( int [] a, int n) { var p = 0; while (p != n) { if (a[p] == -1) { p++; } else { if (a[a[p] - 1] == -1) { Console.WriteLine(a[p]); break ; } else { a[p] = a[a[p] - 1]; a[a[p] - 1] = -1; } } } } public static void Main(String[] args) { int [] a = {1, 2, 4, 3, 4, 5, 6, 3}; var n = a.Length; GFG.find_duplicate(a, n); } } // This code is contributed by aadityaburujwale. |
Javascript
function find_duplicate( a, n) { let p = 0; while (p != n) { if (a[p] == -1) { p++; } else { if (a[a[p] - 1] == -1) { console.log(a[p]); break ; } else { a[p] = a[a[p] - 1]; a[a[p] - 1] = -1; } } } } let a = [1, 2, 4, 3, 4, 5, 6, 3 ]; let n = a.length; find_duplicate(a, n); // This Code is Contributed by akashish__ |
Output
3
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(1)
Another Approach:- Use Hashing to find duplicate element.
Implementation:-
C++
#include <bits/stdc++.h> using namespace std; //function to find duplicate int find_duplicate( int a[], int n) { //map to store frequency unordered_map< int , int > mm; //iterating over array for ( int i=0;i<n;i++){ //storing frequency mm[a[i]]++; //checking for duplicacy if (mm[a[i]]>1) return a[i]; } } int main() { int a[] = { 1, 2, 4, 3, 4, 5, 6, 3 }; int n = sizeof (a) / sizeof (a[0]); cout<<find_duplicate(a, n); return 0; } // This Code is Contributed by shubhamrajput6156 |
Java
// Java code for the above approach: import java.io.*; import java.util.*; class GFG { // function to find duplicate static int find_duplicate( int [] a, int n) { // map to store frequency Map<Integer, Integer> mm = new HashMap<>(); // iterating over array for ( int i = 0 ; i < n; i++) { // storing frequency if (mm.containsKey(a[i])) { int val = mm.get(a[i]); mm.put(a[i], val + 1 ); } else { mm.put(a[i], 1 ); } // checking for duplicacy if (mm.get(a[i]) > 1 ) return a[i]; } return - 1 ; } public static void main(String[] args) { int [] a = { 1 , 2 , 4 , 3 , 4 , 5 , 6 , 3 }; int n = a.length; System.out.print(find_duplicate(a, n)); } } // This code is contributed by sankar. |
Python3
# function to find duplicate def find_duplicate(a, n): # Dictionary to store frequency mm = {} # Iterating over array for i in range (n): # Storing frequency if a[i] in mm: mm[a[i]] + = 1 else : mm[a[i]] = 1 # Checking for duplicacy if mm[a[i]] > 1 : return a[i] # driver code a = [ 1 , 2 , 4 , 3 , 4 , 5 , 6 , 3 ] n = len (a) print (find_duplicate(a, n)) # This code is contributed by redmoonz. |
C#
using System; using System.Collections.Generic; class GFG { // function to find duplicate static int find_duplicate( int [] a, int n) { // map to store frequency Dictionary< int , int > mm = new Dictionary< int , int >(); // iterating over array for ( int i = 0; i < n; i++) { // storing frequency if (mm.ContainsKey(a[i])) { var val = mm[a[i]]; mm.Remove(a[i]); mm.Add(a[i], val + 1); } else { mm.Add(a[i], 1); } // checking for duplicacy if (mm[a[i]] > 1) return a[i]; } return -1; } static void Main( string [] args) { int [] a = { 1, 2, 4, 3, 4, 5, 6, 3 }; int n = a.Length; Console.Write(find_duplicate(a, n)); } } |
Javascript
function findDuplicate(a) { // Create an empty object to store frequency let frequency = {}; // Iterate over the array for (let i = 0; i < a.length; i++) { // If the element is present in the frequency object, increment the frequency if (a[i] in frequency) { frequency[a[i]]++; } else { // If not, set the frequency to 1 frequency[a[i]] = 1; } // Check if the frequency of the current element is greater than 1 if (frequency[a[i]] > 1) { // If yes, return the element return a[i]; } } } // Driver code let arr = [1, 2, 4, 3, 4, 5, 6, 3]; console.log(findDuplicate(arr)); // This code is contributed by lokeshpotta20. |
Output:- 4
Time Complexity:- O(N)
Space Complexity:- O(N)
Contact Us