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.length-1; 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.length-1; 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)