Question :
Given an array of integers nums
containing n + 1
integers where each integer is in the range [1, n]
inclusive.
There is only one repeated number in nums
, return this repeated number.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Logic:

Naive Approach :
 Take input as array
 run 1 loop from i to arr . length  2 location
 run 2nd loop from i to arr . length  1 location
 if arr[ i ] = arr[ j ] then break out of the loop and return the arr [ i ] or arr[ j ]

Sorting :
 Take input as array
 sort the array using library function
 run a loop from i to arr . length  2.
 and check if arr[ i ] = arr[ i+1 ]. If yes then return arr [ i ]

Extraspace :
 Take the input as array
 sort the array using library function
 create an extra[ ] array of arr.length size
 run the loop from i to arr.length 1
 check if extra [ arr [ i ] ] = 0. if yes then make extra [ arr [ i ] ] = 1 and if no then return arr [ i ]

Linked List / Rabbit and Tortoise method:
 Take input as array
 create a linked list and run a loop from i = 0 to i = arr . length
 make i = arr [ i ] and add arr [ i ] to linked list ( as shown in the code )
 take two pointers slow and fast. move slow by one step and fast by two steps
 whenever they will meet put fast on the first element
 and now move fast by one and slow by one until they both meet at a point
 return slow.
import java.util.*;
public class Solution{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0; i < arr.length; i++){
arr[i] = sc.nextInt();
}
//This is Naive approach with Complexity O(N^2)
int repeat = 0;
for(int i = 0; i < arr.length1; i++){
for(int j = i+1; j < arr.length; j++){
if(arr[i] == arr[j]){
repeat = arr[i];
break;
}
}
}
System.out.println("Repeated element through naive approach is: "+repeat);
//This is Sort and Two pointer approach with complexity (O(N*logN)+ O(N))
int repeat2 = 0;
Arrays.sort(arr);
for(int i = 0; i < arr.length1; i++){
if(arr[i] == arr[i+1]){
repeat2 = arr[i];
break;
}
}
System.out.println("Repeated element through sort + two pointer approach is: "+repeat2);
//This is Sort and extra space approach
int repeat3 = 0;
int extra[] = new int[n];
for(int i = 0; i < extra.length; i++){
extra[i] = 0;
}
Arrays.sort(arr);
for(int i = 0 ; i < arr.length; i++ ){
if(extra[arr[i]] != 0){
repeat3 = arr[i];
break;
}else{
extra[arr[i]] = 1;
}
}
System.out.println("Repeated element through sort + extra space is: "+repeat3);
//This is Linked list with tortoise and rabbit method
int repeat4 = 0;
LinkedList<Integer> li = new LinkedList<>();
for(int i = 0; i < arr.length; i++){
i = arr[i];
li.add(arr[i]);
}
Integer nums[] = li.toArray(new Integer[li.size()]);
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];
}
repeat4 = slow;
System.out.println("Repeated elements through linked list approach is: "+repeat4);
}
}
Top comments (0)