Find the only repetitive element between 1 to N-1
Given an array of size N filled with numbers from 1 to N-1 in random order. The array has only one repetitive element. The task is to find the repetitive element.
Examples:
Input: a[] = {1, 3, 2, 3, 4}
Output: 3
Explanation: The number 3 is the only repeating element.Input: a[] = {1, 5, 1, 2, 3, 4}
Output: 1
Naive Approach: To solve the problem follow the below idea:
Use two nested loops. The outer loop traverses through all elements and the inner loop check if the element picked by the outer loop appears anywhere else.
Below is the implementation of the above approach:
C++
// C++ program to find the only repeating // element in an array where elements are // from 1 to N-1. #include <bits/stdc++.h> using namespace std; int findRepeating( int arr[], int N) { for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { if (arr[i] == arr[j]) return arr[i]; } } } // Driver's code int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } // This code is added by Arpit Jain |
Java
// Java program to find the only repeating // element in an array where elements are // from 1 to N-1.using System; public class GFG { static int findRepeating( int [] arr) { for ( int i = 0 ; i < arr.length; i++) { for ( int j = i + 1 ; j < arr.length; j++) { if (arr[i] == arr[j]) return arr[i]; } } return - 1 ; } // Driver's code static public void main(String[] args) { // Code int [] arr = new int [] { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int repeatingNum = findRepeating(arr); // Function call System.out.println(repeatingNum); } } // This code is contributed by phasing17 |
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to N-1. def findRepeating(arr, N): for i in range (N): for j in range (i + 1 , N): if (arr[i] = = arr[j]): return arr[i] # Driver's Code if __name__ = = "__main__" : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] N = len (arr) # Function call print (findRepeating(arr, N)) # This code is contributed by Arpit Jain |
C#
// C# program to find the only repeating // element in an array where elements are // from 1 to N-1. using System; public class GFG { static int findRepeating( int [] arr) { for ( int i = 0; i < arr.Length; i++) { for ( int j = i + 1; j < arr.Length; j++) { if (arr[i] == arr[j]) return arr[i]; } } return -1; } // Driver's code static public void Main() { int [] arr = new int [] { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; // Function call int repeatingNum = findRepeating(arr); Console.WriteLine(repeatingNum); } } // This code is contributed by Mohd Nizam |
Javascript
<script> //Javascript program to find the only repeating // element in an array where elements are // from 1 to N-1. function findRepeating(arr, N){ for (let i = 0; i <N; i++) { for (let j = i + 1; j < N; j++) { if (arr[i] == arr[j]) return arr[i]; } } } // Driver code let arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]; let N = arr.length; // Function call console.log(findRepeating(arr, N)); // This code is contributed by aarohirai2616. </script> |
8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Find the only repetitive element using sorting:
Sort the given input array. Traverse the array and if value of the ith element is not equal to i+1, then the current element is repetitive as value of elements is between 1 and N-1 and every element appears only once except one element.
Follow the below steps to solve the problem:
- Sort the given array.
- Traverse the array and compare the array elements with its index
- if arr[i] != i+1, it means that arr[i] is repetitive, So Just return arr[i].
- Otherwise, the array does not contain duplicates from 1 to n-1, In this case, return -1
Below is the implementation of the above approach:
C++
// CPP program to find the only repeating // element in an array where elements are // from 1 to N-1. #include <bits/stdc++.h> using namespace std; int findRepeating( int arr[], int N) { sort(arr, arr + N); // sort array for ( int i = 0; i < N; i++) { // compare array element with its index if (arr[i] != i + 1) { return arr[i]; } } return -1; } // driver's code int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } // this code is contributed by devendra solunke |
Java
// Java program to find the only repeating // element in an array where elements are // from 1 to N-1. import java.util.Arrays; public class GFG { static int findRepeating( int [] arr, int N) { Arrays.sort(arr); // sort array for ( int i = 0 ; i < N; i++) { // compare array element with its index if (arr[i] != i + 1 ) { return arr[i]; } } return - 1 ; } // Driver's code static public void main(String[] args) { int [] arr = new int [] { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int N = arr.length; // Function call int repeatingNum = findRepeating(arr, N); System.out.println(repeatingNum); } } // This code is contributed by Abhijeet Kumar(abhijeet19403) |
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to N-1. def findRepeating(arr, N): arr.sort() for i in range ( 1 , N): if (arr[i] ! = i + 1 ): return arr[i] # Driver's Code if __name__ = = "__main__" : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] N = len (arr) # Function call print (findRepeating(arr, N)) # This code is contributed by Arpit Jain |
C#
// C# program to find the only repeating element in an array // where elements are from 1 to N-1. using System; public class GFG { static int findRepeating( int [] arr, int N) { Array.Sort(arr); // sort array for ( int i = 0; i < N; i++) { // compare array element with its index if (arr[i] != i + 1) { return arr[i]; } } return -1; } // Driver's code static public void Main() { int [] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = arr.Length; // Function call int repeatingNum = findRepeating(arr, N); Console.WriteLine(repeatingNum); } } // This code is contributed by lokesh (lokeshmvs21). |
Javascript
<script> //Javascript program to find the only repeating // element in an array where elements are // from 1 to N-1. function findRepeating(arr, N){ arr.sort(); for (let i = 0; i < N; i++) { // compare array element with its index if (arr[i] != i + 1) { return arr[i]; } } return -1; } // Driver code let arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]; let N = arr.length; // Function call console.log(findRepeating(arr, N)); // This code is contributed by aarohirai2616. </script> |
8
Time complexity: O(N * log N)
Auxiliary Space: O(1)
Find the only repetitive element using a frequency array:
Use a array to store frequency of elements appeared in array. If frequency of element is greater than one,then return it.
C++
#include <bits/stdc++.h> using namespace std; int findRepeating( int arr[], int N) { int freq[N+1]; // initializing array for all memset (freq, 0, sizeof (freq)); // elements with frequency 0. for ( int i = 0; i < N; i++) { freq[arr[i]]++; } for ( int i = 0; i < N; i++) { if (freq[arr[i]] > 1) { return arr[i]; } } return -1; } int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } |
Java
public class Main { static int findRepeating( int arr[], int N) { int [] freq = new int [N + 1 ]; for ( int i = 0 ; i < N; i++) { freq[arr[i]]++; } for ( int i = 0 ; i < N; i++) { if (freq[arr[i]] > 1 ) { return arr[i]; } } return - 1 ; } public static void main(String[] args) { int arr[] = { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int N = arr.length; // Function call System.out.println(findRepeating(arr, N)); } } |
Python3
def findRepeating(arr, N): freq = [ 0 ] * (N + 1 ) for i in range (N): freq[arr[i]] + = 1 for i in range (N): if freq[arr[i]] > 1 : return arr[i] return - 1 arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] N = len (arr) # Function call print (findRepeating(arr, N)) |
C#
using System; using System.Linq; class MainClass { public static int findRepeating( int [] arr, int N) { int [] freq = new int [N + 1]; for ( int i = 0; i < N; i++) { freq[arr[i]]++; } for ( int i = 0; i < N; i++) { if (freq[arr[i]] > 1) { return arr[i]; } } return -1; } public static void Main ( string [] args) { int [] arr = {9, 8, 2, 6, 1, 8, 5, 3, 4, 7}; int N = arr.Length; // Function call Console.WriteLine(findRepeating(arr, N)); } } |
Javascript
function findRepeating(arr, N) { var freq = new Array(N + 1).fill(0); for ( var i = 0; i < N; i++) { freq[arr[i]]++; } for ( var i = 0; i < N; i++) { if (freq[arr[i]] > 1) { return arr[i]; } } return -1; } var arr = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]; var N = arr.length; // Function call console.log(findRepeating(arr, N)); |
8
Time Complexity: O(N)
Auxiliary Space: O(N)
Find the only repetitive element using the hash set:
Use a hash table to store elements visited. If an already visited element appears again, return it.
Follow the below steps to solve the problem:
- Create a hash set to store the visited elements
- Traverse the array
- If the given element is already present in the hash set then, return this element
- else insert this element into the hash set
- Return -1, if no repeating is found
Below is the implementation of the above approach:
C++
// C++ program to find the only repeating // element in an array where elements are // from 1 to N-1. #include <bits/stdc++.h> using namespace std; int findRepeating( int arr[], int N) { unordered_set< int > s; for ( int i = 0; i < N; i++) { if (s.find(arr[i]) != s.end()) return arr[i]; s.insert(arr[i]); } // If input is correct, we should // never reach here return -1; } // Driver's code int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } |
Java
import java.util.*; // Java program to find the only repeating // element in an array where elements are // from 1 to N-1. class GFG { static int findRepeating( int arr[], int N) { HashSet<Integer> s = new HashSet<Integer>(); for ( int i = 0 ; i < N; i++) { if (s.contains(arr[i])) return arr[i]; s.add(arr[i]); } // If input is correct, we should // never reach here return - 1 ; } // Driver's code public static void main(String[] args) { int arr[] = { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int N = arr.length; // Function call System.out.println(findRepeating(arr, N)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find the only # repeating element in an array # where elements are from 1 to n-1. def findRepeating(arr, N): s = set () for i in range (N): if arr[i] in s: return arr[i] s.add(arr[i]) # If input is correct, we should # never reach here return - 1 # Driver code if __name__ = = "__main__" : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 ] N = len (arr) # Function call print (findRepeating(arr, N)) # This code is contributed # by Shrikant13 |
C#
// C# program to find the only repeating // element in an array where elements are // from 1 to N-1. using System; using System.Collections.Generic; class GFG { static int findRepeating( int [] arr, int N) { HashSet< int > s = new HashSet< int >(); for ( int i = 0; i < N; i++) { if (s.Contains(arr[i])) return arr[i]; s.Add(arr[i]); } // If input is correct, we should // never reach here return -1; } // Driver code public static void Main(String[] args) { int [] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = arr.Length; // Function call Console.WriteLine(findRepeating(arr, N)); } } // This code has been contributed by 29AjayKumar |
Javascript
// JavaScript program to find the only repeating // element in an array where elements are // from 1 to n-1. function findRepeating(arr,n) { s = new Set(); for (let i = 0; i < n; i++) { if (s.has(arr[i])) return arr[i]; s.add(arr[i]); } // If input is correct, we should // never reach here return -1; } // driver code let arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]; let n = arr.length; document.write(findRepeating(arr, n)); // This code is contributed by shinjanpatra. |
8
Time Complexity: O(N)
Auxiliary Space: O(N)
Find the only repetitive element using the Sum of first N elements:
We know sum of first n-1 natural numbers is (N – 1)*N/2. We compute sum of array elements and subtract natural number sum from it to find the only missing element.
Follow the below steps to solve the problem:
- Calculate the sum of array elements and the sum of first (N-1) natural numbers
- Return (array sum) – ((N-1) natural numbers sum)
Below is the implementation of the above approach:
C++
// CPP program to find the only repeating // element in an array where elements are // from 1 to N-1. #include <bits/stdc++.h> using namespace std; int findRepeating( int arr[], int N) { // Find array sum and subtract sum // first N-1 natural numbers from it // to find the result. return accumulate(arr, arr + N, 0) - ((N - 1) * N / 2); } // Driver's code int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } |
Java
// Java program to find the only repeating // element in an array where elements are // from 1 to N-1. import java.io.*; import java.util.*; class GFG { static int findRepeating( int [] arr, int N) { // Find array sum and subtract sum // first n-1 natural numbers from it // to find the result. int sum = 0 ; for ( int i = 0 ; i < N; i++) sum += arr[i]; return sum - (((N - 1 ) * N) / 2 ); } // Driver's code public static void main(String args[]) { int [] arr = { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int N = arr.length; // Function call System.out.println(findRepeating(arr, N)); } } // This code is contributed by rachana soma |
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to N-1. def findRepeating(arr, N): # Find array sum and subtract sum # first n-1 natural numbers from it # to find the result. return sum (arr) - (((N - 1 ) * N) / / 2 ) # Driver's Code if __name__ = = "__main__" : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] N = len (arr) # Function call print (findRepeating(arr, N)) # This code is contributed # by mohit kumar |
C#
// C# program to find the only repeating // element in an array where elements are // from 1 to N-1. using System; class GFG { static int findRepeating( int [] arr, int N) { // Find array sum and subtract sum // first N-1 natural numbers from it // to find the result. int sum = 0; for ( int i = 0; i < N; i++) sum += arr[i]; return sum - (((N - 1) * N) / 2); } // Driver's code public static void Main(String[] args) { int [] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = arr.Length; // Function call Console.WriteLine(findRepeating(arr, N)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
// javascript program to find the only repeating // element in an array where elements are // from 1 to n-1. function findRepeating(arr , n) { // Find array sum and subtract sum // first n-1 natural numbers from it // to find the result. var sum = 0; for (i = 0; i < n; i++) sum += arr[i]; return sum - (((n - 1) * n) / 2); } // Driver code var arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]; var n = arr.length; document.write(findRepeating(arr, n)); // This code is contributed by Rajput-Ji |
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Note: This approach Causes overflow for large arrays.
Find the only repetitive element using XOR:
The idea is based on the fact that x ^ x = 0 and if x ^ y = z then x ^ z = y
Follow the below steps to solve the problem:
- Compute XOR of elements from 1 to n-1.
- Compute XOR of array elements.
- XOR of the above two would be our result.
Below is the implementation of the above approach:
C++
// CPP program to find the only repeating // element in an array where elements are // from 1 to N-1. #include <bits/stdc++.h> using namespace std; int findRepeating( int arr[], int N) { // res is going to store value of // 1 ^ 2 ^ 3 .. ^ (N-1) ^ arr[0] ^ // arr[1] ^ .... arr[N-1] int res = 0; for ( int i = 0; i < N - 1; i++) res = res ^ (i + 1) ^ arr[i]; res = res ^ arr[N - 1]; return res; } // Driver code int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } |
Java
// Java program to find the only repeating // element in an array where elements are // from 1 to N-1. import java.io.*; class GFG { static int findRepeating( int arr[], int N) { // res is going to store value of // 1 ^ 2 ^ 3 .. ^ (N-1) ^ arr[0] ^ // arr[1] ^ .... arr[n-1] int res = 0 ; for ( int i = 0 ; i < N - 1 ; i++) res = res ^ (i + 1 ) ^ arr[i]; res = res ^ arr[N - 1 ]; return res; } // Driver code public static void main(String[] args) { int arr[] = { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int N = arr.length; // Function call System.out.println(findRepeating(arr, N)); } } // This code is contributed by // Smitha Dinesh Semwal. |
Python3
# Python3 program to find the only # repeating element in an array where # elements are from 1 to N-1. def findRepeating(arr, N): # res is going to store value of # 1 ^ 2 ^ 3 .. ^ (N-1) ^ arr[0] ^ # arr[1] ^ .... arr[n-1] res = 0 for i in range ( 0 , N - 1 ): res = res ^ (i + 1 ) ^ arr[i] res = res ^ arr[N - 1 ] return res # Driver code if __name__ = = "__main__" : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] N = len (arr) # Function call print (findRepeating(arr, N)) # This code is contributed by Smitha Dinesh Semwal. |
C#
// C# program to find the only repeating // element in an array where elements are // from 1 to N-1. using System; public class GFG { static int findRepeating( int [] arr, int N) { // res is going to store value of // 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^ // arr[1] ^ .... arr[N-1] int res = 0; for ( int i = 0; i < N - 1; i++) res = res ^ (i + 1) ^ arr[i]; res = res ^ arr[N - 1]; return res; } // Driver code public static void Main(String[] args) { int [] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = arr.Length; // Function call Console.WriteLine(findRepeating(arr, N)); } } // This code is contributed by Rajput-Ji |
Javascript
// JavaScript program to find the only repeating // element in an array where elements are // from 1 to n-1. function findRepeating(arr,n) { // res is going to store value of // 1 ^ 2 ^ 3 .. ^ (n-1) ^ arr[0] ^ // arr[1] ^ .... arr[n-1] let res = 0; for (let i=0; i<n-1; i++) res = res ^ (i+1) ^ arr[i]; res = res ^ arr[n-1]; return res; } // driver code let arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]; let n = arr.length; document.write(findRepeating(arr, n)); |
PHP
<?php // PHP program to find the only repeating // element in an array where elements are // from 1 to n-1. function findRepeating( $arr , $N ) { // res is going to store value of // 1 ^ 2 ^ 3 .. ^ (N-1) ^ arr[0] ^ // arr[1] ^ .... arr[N-1] $res = 0; for ( $i = 0; $i < $N - 1; $i ++) $res = $res ^ ( $i + 1) ^ $arr [ $i ]; $res = $res ^ $arr [ $N - 1]; return $res ; } // Driver Code $arr = array (9, 8, 2, 6, 1, 8, 5, 3, 4, 7); $N = sizeof( $arr ) ; // Function call echo findRepeating( $arr , $N ); // This code is contributed by ajit ?> |
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the only repetitive element using indexing:
As there are only positive numbers, so visit the index equal to the current element and make it negative. If an index value is already negative, then it means that current element is repeated
Follow the below steps to solve the problem:
- Iterate through the array.
- For every index visit arr[arr[i]], if it is positive change the sign of elements at that index, else print the element.
Below is the implementation of the above approach:
C++
// CPP program to find the only // repeating element in an array // where elements are from 1 to N-1. #include <bits/stdc++.h> using namespace std; // Function to find repeated element int findRepeating( int arr[], int N) { int missingElement = 0; // indexing based for ( int i = 0; i < N; i++) { int element = arr[ abs (arr[i])]; if (element < 0) { missingElement = arr[i]; break ; } arr[ abs (arr[i])] = -arr[ abs (arr[i])]; } return abs (missingElement); } // Driver code int main() { int arr[] = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << findRepeating(arr, N); return 0; } |
Java
// Java program to find the only // repeating element in an array // where elements are from 1 to N-1. import java.lang.Math.*; class GFG { // Function to find repeated element static int findRepeating( int arr[], int N) { int missingElement = 0 ; // indexing based for ( int i = 0 ; i < N; i++) { int absVal = Math.abs(arr[i]); int element = arr[absVal]; if (element < 0 ) { missingElement = arr[i]; break ; } absVal = Math.abs(arr[i]); arr[absVal] = -arr[absVal]; } return Math.abs(missingElement); } // Driver code public static void main(String[] args) { int arr[] = { 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 }; int N = arr.length; // Function call System.out.println(findRepeating(arr, N)); } } // This code is contributed by // Smitha Dinesh Semwal. |
Python3
# Python3 program to find the only # repeating element in an array # where elements are from 1 to N-1. # Function to find repeated element def findRepeating(arr, N): missingElement = 0 # indexing based for i in range ( 0 , N): element = arr[ abs (arr[i])] if (element < 0 ): missingElement = arr[i] break arr[ abs (arr[i])] = - arr[ abs (arr[i])] return abs (missingElement) # Driver code if __name__ = = "__main__" : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] N = len (arr) # Function call print (findRepeating(arr, N)) # This code is contributed by Smitha Dinesh Semwal. |
C#
// C# program to find the only // repeating element in an array // where elements are from 1 to N-1. using System; public class GFG { // Function to find repeated element static int findRepeating( int [] arr, int N) { int missingElement = 0; // indexing based for ( int i = 0; i < N; i++) { int absVal = Math.Abs(arr[i]); int element = arr[absVal]; if (element < 0) { missingElement = arr[i]; break ; } absVal = Math.Abs(arr[i]); arr[absVal] = -arr[absVal]; } return Math.Abs(missingElement); } // Driver Code public static void Main( string [] args) { int [] arr = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; int N = arr.Length; // Function call Console.WriteLine(findRepeating(arr, N)); } } // this code is contributed by phasing17 |
Javascript
// JavaScript program for the above approach; // Function to find repeated element function findRepeating(arr, n) { let missingElement = 0; // indexing based for (let i = 0; i < n; i++) { let absVal = Math.abs(arr[i]); let element = arr[absVal]; if (element < 0) { missingElement = arr[i]; break ; } let absVal = Math.abs(arr[i]); arr[absVal] = -arr[absVal]; } return Math.abs(missingElement); } // driver code let arr = [5, 4, 3, 9, 8, 9, 1, 6, 2, 5]; let n = arr.length; document.write(findRepeating(arr, n)); // This code is contributed by Potta Lokesh |
PHP
<?php // PHP program to find the only // repeating element in an array // where elements are from 1 to n-1. // Function to find repeated elements function findRepeating( $arr , $N ) { $missingElement = 0; // indexing based for ( $i = 0; $i < $N ; $i ++) { $element = $arr [ abs ( $arr [ $i ])]; if ( $element < 0) { $missingElement = $arr [ $i ]; break ; } $arr [ abs ( $arr [ $i ])] = - $arr [ abs ( $arr [ $i ])]; } return abs ( $missingElement ); } // Driver Code $arr = array (5, 4, 3, 9, 8, 9, 1, 6, 2, 5); $N = sizeof( $arr ); // Function call echo findRepeating( $arr , $N ); // This code is contributed by ajit ?> |
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the only repetitive element using Linked-List cycle method:
Use two pointers the fast and the slow. The fast one goes forward two steps each time, while the slow one goes only step each time. They must meet the same item when slow==fast.
In fact, they meet in a circle, the duplicate number must be the entry point of the circle when visiting the array from array[0].
Next we just need to find the entry point. We use a point(we can use the fast one before) to visit from the beginning with one step each time, do the same job to slow. When fast==slow, they meet at the entry point of the circle.
Follow the below steps to solve the problem:
- Declare two integer pointers as slow and fast
- Move the slow pointer one time and fast pointer two times, until slow is not equal to fast
- Once they are equal then again start the fast pointer from the start of the array
- Move both the pointers, one step at a time until both of them are equal
- Return slow or fast pointer as the answer
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int findDuplicate(vector< int >& nums) { int slow = nums[0]; //slow pointer int fast = nums[0]; //fast pointer do { slow = nums[slow]; //moves one step-->if speed is x fast = nums[nums[fast]]; //it moves fast than slow pointer-->speed is 2x } while (slow != fast); fast = nums[0]; //initialize fast to the starting point //loop untill both pointer will meet at the same point while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } //return duplicate number return slow; } // Driver code int main() { vector< int > v{ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; // Function call int ans = findDuplicate(v); cout << ans << endl; return 0; } |
Java
import java.io.*; import java.util.*; class GFG { public static int findDuplicate(ArrayList<Integer> nums) { int slow = nums.get( 0 ); int fast = nums.get( 0 ); do { slow = nums.get(slow); fast = nums.get(nums.get(fast)); } while (slow != fast); fast = nums.get( 0 ); while (slow != fast) { slow = nums.get(slow); fast = nums.get(fast); } return slow; } public static void main(String[] args) { ArrayList<Integer> arr = new ArrayList<Integer>( Arrays. asList( 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ) ); // Function call int ans = findDuplicate(arr); System.out.println(ans); } } // This code is contributed by adityapatil12 |
Python3
class GFG : @staticmethod def findDuplicate( nums) : slow = nums[ 0 ] fast = nums[ 0 ] while True : slow = nums[slow] fast = nums[nums[fast]] if ((slow ! = fast) = = False ) : break fast = nums[ 0 ] while (slow ! = fast) : slow = nums[slow] fast = nums[fast] return slow @staticmethod def main( args) : arr = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] # Function call ans = GFG.findDuplicate(arr) print (ans) if __name__ = = "__main__" : GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# code for the above approach using System; public class GFG { static int findDuplicate( int [] nums) { int slow = nums[0]; int fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); fast = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } static public void Main() { // Code int [] v = { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; // Function call int ans = findDuplicate(v); Console.Write(ans); } } // This code is contributed by lokesh. |
Javascript
function findDuplicate(nums){ var slow = nums[0]; var fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); fast = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } var arr = [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ]; // Function call var ans = findDuplicate(arr); console.log(ans); // This code is contributed by aadityaburujwale. |
8
Time Complexity: O(N)
Auxiliary Space: O(1)
Find the only repetitive element Using Binary Search:
implementation is given below:- |
C++
#include <bits/stdc++.h> using namespace std; int findDuplicate(vector< int >& nums) { int low = 1, high = nums.size() - 1, cnt; while (low <= high) { int mid = low + (high - low) / 2; cnt = 0; // cnt number less than equal to mid for ( int n : nums) { if (n <= mid) ++cnt; } // binary search on left if (cnt <= mid) low = mid + 1; else // binary search on right high = mid - 1; } return low; } // Driver code int main() { vector< int > v{ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; // Function call int ans = findDuplicate(v); cout << ans << endl; //8 return 0; } //priyapramanick17 |
Java
import java.util.ArrayList; import java.util.List; public class FindDuplicate { public static void main(String[] args) { List<Integer> nums = new ArrayList<>(); nums.add( 9 ); nums.add( 8 ); nums.add( 2 ); nums.add( 6 ); nums.add( 1 ); nums.add( 8 ); nums.add( 5 ); nums.add( 3 ); nums.add( 4 ); nums.add( 7 ); // Function call int ans = findDuplicate(nums); System.out.println(ans); // 8 } public static int findDuplicate(List<Integer> nums) { int low = 1 ; int high = nums.size() - 1 ; int cnt; while (low <= high) { int mid = low + (high - low) / 2 ; cnt = 0 ; // Count the number of elements less than or equal to mid for ( int n : nums) { if (n <= mid) cnt++; } // Binary search on the left if (cnt <= mid) low = mid + 1 ; else // Binary search on the right high = mid - 1 ; } return low; } } |
Python
def find_duplicate(nums): # Initialize the low and high values for binary search low = 1 high = len (nums) - 1 while low < = high: mid = low + (high - low) / / 2 # Calculate the middle index cnt = 0 # Count the numbers less than or equal to mid for n in nums: if n < = mid: cnt + = 1 # Perform binary search on the left half if cnt < = mid: low = mid + 1 else : # Perform binary search on the right half high = mid - 1 return low # Driver code if __name__ = = "__main__" : v = [ 9 , 8 , 2 , 6 , 1 , 8 , 5 , 3 , 4 , 7 ] # Function call ans = find_duplicate(v) print (ans) # Output should be 8 |
C#
using System; using System.Collections.Generic; class Program { // Function to find the duplicate element in a list of integers public static int FindDuplicate(List< int > nums) { int low = 1; int high = nums.Count - 1; int cnt; while (low <= high) { int mid = low + (high - low) / 2; cnt = 0; // Count numbers less than or equal to mid in the list foreach ( int n in nums) { if (n <= mid) { cnt++; } } // If the count of numbers less than or equal to mid is less than or equal to mid, // it means the duplicate element is on the right side of mid. if (cnt <= mid) { low = mid + 1; // Binary search on the right side } else { high = mid - 1; // Binary search on the left side } } return low; // The duplicate element is found at 'low' } static void Main( string [] args) { List< int > nums = new List< int > { 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 }; // Function call int ans = FindDuplicate(nums); Console.WriteLine(ans); // Print the duplicate element } } |
Javascript
function findDuplicate(nums) { let low = 1; let high = nums.length - 1; let cnt; while (low <= high) { let mid = low + Math.floor((high - low) / 2); cnt = 0; // cnt number less than equal to mid for (let n of nums) { if (n <= mid) ++cnt; } // binary search on left if (cnt <= mid) low = mid + 1; else // binary search on right high = mid - 1; } return low; } // Driver code let v = [9, 8, 2, 6, 1, 8, 5, 3, 4, 7]; // Function call let ans = findDuplicate(v); console.log(ans); //8 |
Contact Us