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 codeint 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 approachusing 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. |
Output
8
Time Complexity: O(N)
Auxiliary Space: O(1)
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 codeint 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 Codeif __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 codelet arr= [ 9, 8, 2, 6, 1, 8, 5, 3, 4, 7 ];let N = arr.length;// Function callconsole.log(findRepeating(arr, N));// This code is contributed by aarohirai2616.</script> |
Output
8
Time Complexity: O(N2)
Auxiliary Space: O(1)