def findDuplicate(arr):
# Write your code here
b=[]
for i in arr:
if i not in b :
b.append(i)
else:
return i
Problem of the day
You are given an array ‘ARR’ of size ‘N’ containing each number between 1 and ‘N’ - 1 at least once. There is a single integer value that is present in the array twice. Your task is to find the duplicate integer value present in the array.
For example:
Consider ARR = [1, 2, 3, 4, 4], the duplicate integer value present in the array is 4. Hence, the answer is 4 in this case.
Note :
A duplicate number is always present in the given array.
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains a single integer, 'N', denoting the number of elements in the array.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
Output Format:
For each test case, print a single integer - the duplicate element in the array.
Print the output of each test case in a separate line.
1 <= T <= 10
2 <= N <= 10 ^ 5
1 <= ARR[i] <= N - 1
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'.
Time limit: 1 sec
2
5
4 2 1 3 1
7
6 3 1 5 4 3 2
1
3
For the first test case,
The duplicate integer value present in the array is 1. Hence, the answer is 1 in this case.
For the second test case,
The duplicate integer value present in the array is 3. Hence, the answer is 3 in this case.
2
6
5 1 2 3 4 2
9
8 7 2 5 4 7 1 3 6
2
7
1. Simply calculate the frequency of each value.
2. Try to optimise the above approach by using an array to store the frequencies.
3. Think of a solution using Floyd’s cycle finding algorithm.
4. Try to think of a solution based on bitwise XOR.
A simple method is to traverse through the array ARR to find the frequency of each number in the given array, and we will check if the frequency of the number is more than 1.
Therefore, our approach will be to iterate currentNumber from 1 to N - 1. In each iteration, we will traverse through the array ARR to find the frequency of currentNumber in the array. We will check if the frequency is more than 1, then there is a duplicate of the number currentNumber in the array ARR. In the end, we will return the duplicate integer value present in the array.
Algorithm:
O(N ^ 2), where N denotes the number of elements in the array.
We are doing N - 1 iteration, and in each iteration, we are traversing through the array ARR to find the frequency of the number in the given array that takes O(N) time. Hence, the overall Time Complexity = O(N) * (N) = O(N ^ 2).
O(1).
Constant space is being used. Hence, the overall Space Complexity is O(1).
Interview problems
Find Duplicate in array. Python
def findDuplicate(arr):
# Write your code here
b=[]
for i in arr:
if i not in b :
b.append(i)
else:
return i
Interview problems
Solution:
int findDuplicate(vector<int> &arr)
{
int ans = 0;
for(int i =0; i<arr.size(); i++){
ans = ans^arr[i];
}
for(int i = 1; i<arr.size(); i++){
ans = ans^i;
}
return ans;
}
Interview problems
optimal solution
#include<bits/stdc++.h>
int findDuplicate(vector<int> &arr)
{
// Write your code here
unordered_map<int,int>ans;
for(int i=0;i<arr.size();i++){
ans[arr[i]]++;
if(ans[arr[i]]>1){
return arr[i];
}
}
return 0;
}
Interview problems
Most Optimal & Single iteration Xor Based Solution
#include <unordered_set>
int findDuplicate(vector<int> &arr)
{
// Write your code here
int n = arr.size(); // Get the size of the array
int Xor = 0; // Initialize a variable Xor to store the XOR of elements
// Iterate through the array
for(int i = 0; i < n; i++) {
/*
Perform XOR between:
- The current element of the array (arr[i])
- The index (i)
This will help cancel out all unique elements.
*/
Xor = Xor ^ arr[i] ^ i;
}
// Return the result, which is the duplicate element
return Xor;
}
Why does this work?
Result: After the loop finishes, the variable Xor will hold the value of the duplicate element, which is then returned.
Interview problems
Duplicate in Array
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Solution {
public static int findDuplicate(ArrayList<Integer> arr) {
Set<Integer> s=new HashSet<>();
for(int i=0;i<arr.size();i++){
if(s.contains(arr.get(i))){
return arr.get(i);
}
s.add(arr.get(i));
}
return -1;
}
}
Interview problems
Java
import java.util.ArrayList;
public class Solution {
public static int findDuplicate(ArrayList<Integer> arr) {
int ans = 0;
for(int i=0; i<arr.size(); i++) {
ans ^= arr.get(i);
}
for(int i=1; i<arr.size(); i++) {
ans = ans ^ i;
}
return ans;
}
}
Interview problems
1 Line python solution using Arithmentic Progression
def findDuplicate(arr): l = len(arr)-1
# Sum of all elements -(sum of numbers from 1 to n-1) return sum(arr) - int(l*(l+1)/2)
Interview problems
O(n) best and easy solution in python
def findDuplicate(arr):
# Write your code here
arr.sort()
for i in range(len(arr)):
j=i+1
if arr[i]==arr[j]:
return arr[i]
break
pass
Interview problems
Find dupicate in Array
int findDuplicate(vector<int> &arr)
{
// Write your code here
int ans = 0;
for(int i = 0; i<arr.size();i++){
ans = ans^arr[i];
}
for(int i =0; i<arr.size();i++){
ans = ans^i;
}
return ans;
}
Interview problems
Easy JAVA Solution with constant Space
import java.util.ArrayList;
public class Solution {
public static int findDuplicate(ArrayList<Integer> arr) {
// Write your code here.
int n = arr.size();
int l = 0;
int r = n-1;
while(l < r){
int mid = l + (r-l)/2;
int count = 0;
for(int x : arr){
if(x <= mid){
count++;
}
}
if(count > mid){
r = mid;
}else {
l = mid+1;
}
}
return l;
}
}