CODEWITHSUNDEEP
arraysalgorithm
geeky
geeky

Reputation: 145

Find the missing number in two sorted arrays

I encountered an interview question.

Given two sorted arrays.
Initially both have set set of elements but one element is removed from one array.
Find the element removed.
Constraint is we have to done it inplace in O(logn) For ex: 

arr1[]={1,2,3,8,12,16};
arr2[]={1,2,8,12,16};

element removed is 3

Upvotes: 0

Views: 472

Answers (1)

Giorgi Nakeuri
Giorgi Nakeuri

Reputation: 35780

I am typing from mobile, so it is a pseudo code, but you will get it:

take arr1.len / 2. It is 3. Check arr1[3] and arr2[3]. If they equal then missing vsalue is in index greater than 3 else less than 3. Here we get 8 and 12. So missing is before. We take index 3/2=1. Compare arr1[1] and arr2[1]. They are equal, so missing is after index 1 and before 3. So it is arr1[2] = 3.

This is the idea. You are doing a binary search, deviding searvh area by half everytime. You take left or right part of the array depending on comparing. You just need to implement this and do some checks, but the idea is clear I think.

Upvotes: 5

Related Questions