1

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?

Improve this question
7
  • arrays are always sorted? Commented May 10, 2016 at 16:07
  • do the arrays always contain integers? Commented May 10, 2016 at 16:08
  • @Joni yes always integers Commented May 10, 2016 at 16:13
  • I believe the best solution is; Am I correct? Without a measure for quality/best, I don't see a way to tell. Then, I don't think you need to look at O(n) elements, which your approaches do. (Oh, and please specify whether the elements that are in the 2nd array are in the same order as in the 1st.) Commented May 10, 2016 at 17:40
  • @greybeard not in the same order. How would you do this without O(n)? Commented May 10, 2016 at 18:03

3 Answers 3

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I like this answer because its what an interviewer might be looking for
Thanks, actually I learned this when I was preparing for an interview :)
0

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.

Improve this answer

1 Comment

Thanks! I'm glad I was able to help. :-)
0

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;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.