// Method-2 : Time Complexity : O(n), Auxiliary Space : O(1) import java.util.*; import java.io.*; class GFG { static int repeat(int arr[], int n) { int slow = arr[0], fast = arr[0]; do{ slow = arr[slow]; fast = arr[arr[fast]]; }while(slow != fast); slow = arr[0]; while(slow != fast) { slow = arr[slow]; fast = arr[fast]; } return slow; } public static void main(String args[]) { int arr[] = {1, 3, 2, 4, 6, 5, 7, 3}, n= 8; System.out.println(repeat(arr, n)); // OUTPUT : 3 } } // Method-1 : Time Complexity : O(n), Auxiliary Space : O(n) import java.util.*; import java.io.*; class GFG { static int repeat(int arr[], int n) { boolean visit[] = new boolean[n]; for(int i = 0; i < n; i++) { if(visit[arr[i]]) return arr[i]; visit[arr[i]] = true; } return -1; } public static void main(String args[]) { int arr[] = {0, 2, 1, 3, 2, 2}, n= 6; System.out.println(repeat(arr, n)); // OUTPUT : 2 } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter