CODEWITHSUNDEEP
algorithm
user3259176
user3259176

Reputation:

Algorithm: find the missing element from 2 given arrays, second array is duplicate

Find the missing element from the given 2 arrays, second array is duplicate.

Example: array 1: [1,2,3,4,5,6,7] array 2: [1,3,4,5,6,7]

I read about using hashmaps and other complex approaches, but I believe the best solution is:

1) Add all elements of array1 and array2 separately, such that we have sum1 and sum2, then the answer is |sum2 - sum1|

2) XOR all elements of array1 and array2 separately, such that we have xor1 and xor2. Here xor1 is always from the complete array. The missing element will be xor2 XOR xor1 (from XOR applications http://www.codeproject.com/Articles/2983/XOR-tricks-for-RAID-data-protection)

Edit: arrays not sorted

Am I correct?

Upvotes: 1

Views: 486

Answers (3)

Vidhya Ambethkar
Vidhya Ambethkar

Reputation: 1

I coded for filtering the missing numbers for arrays containing items that has more than one frequency .But time limit is exceeded for size 10^5.Any logic to reduce time complexity is appreciated.

// Missing numbers

// Write your code here
 public static List<Integer> missingNumbers(List<Integer> arr,List<Integer> brr){
Collections.sort(arr);
Collections.sort(brr);
Set<Integer> list = new HashSet<>();
for(int s:brr){
   if(arr.contains(s)){
       if(Collections.frequency(arr,s)!=Collections.frequency(brr,s)){
           list.add(s);
       }
   }
   else{
       list.add(s);
   }
}
ArrayList<Integer> list1= new ArrayList<>(list);
Collections.sort(list1);
return list1;
}

Upvotes: 0

blazs
blazs

Reputation: 4845

Yes, your algorithm is correct, assuming the array contains integers. The proof easily follows from the fact that x^x=0 if and only if x=x. It even works in the case the array contains duplicates.

Proof sketch. Let A be an array of n integers and let B be a copy of A with one element removed. Define xorA := A[0] ^ A[1] ^ ... ^ A[n-1] and xorB := B[0] ^ ... ^ B[n-2]. Since each element, except the missing one, appears even number of times, xorA ^ xorB will equal the missing element which appears odd number of times---all others cancel out because x^x=0.

Upvotes: 0

fcat
fcat

Reputation: 1251

First answer may cause an integer overflow in case of very large numbers.

Second options is better from all aspects. In addition, 1st array does not have to be the containing one. You can start XOR'ing from the beginning of the first array until the last element of the second. You will end up with the unique element in union of both arrays. It costs for O(n) complexity.

Upvotes: 1

Related Questions