CODEWITHSUNDEEP
algorithm
Rajendra Uppal
Rajendra Uppal

Reputation: 19924

Find unique common element from 3 arrays

Original Problem:
I have 3 boxes each containing 200 coins, given that there is only one person who has made calls from all of the three boxes and thus there is one coin in each box which has same fingerprints and rest of all coins have different fingerprints. You have to find the coin which contains same fingerprint from all of the 3 boxes. So that we can find the fingerprint of the person who has made call from all of the 3 boxes.

Converted problem:
You have 3 arrays containing 200 integers each. Given that there is one and only one common element in these 3 arrays. Find the common element.
Please consider solving this for other than trivial O(1) space and O(n^3) time.

Upvotes: 6

Views: 6926

Answers (8)

Khan Mawaz
Khan Mawaz

Reputation: 31

//Begineers Code using Binary Search that's pretty Easy

// bool BS(int arr[],int low,int high,int target)
// {
//     if(low>high)
//     return false;
    
//     int mid=low+(high-low)/2;
    
//     if(target==arr[mid])
//     return 1;
    
//     else if(target<arr[mid])
//     BS(arr,low,mid-1,target);
    
//     else
//     BS(arr,mid+1,high,target);
// }
//   vector <int> commonElements (int A[], int B[], int C[], int n1, int n2, int n3)
//     {
//         vector<int> ans;
//         for(int i=0;i<n2;i++)
//         {
//             if(i>0)
//             {
//                 if(B[i-1]==B[i])
//                 continue;
//             }
//             //The above if block is to remove duplicates
//             //In the below code we are searching an element form array B in both the arrays A and B;
//             if(BS(A,0,n1-1,B[i]) && BS(C,0,n3-1,B[i]))
//             {
//                 ans.push_back(B[i]);
//             }
        
//         }
//         return ans;
//     }

Upvotes: 0

Rex Kerr
Rex Kerr

Reputation: 167891

If you want the fastest* answer:

  • Sort one array--time is N log N.
  • For each element in the second array, search the first. If you find it, add 1 to a companion array; otherwise add 0--time is N log N, using N space.
  • For each non-zero count, copy the corresponding entry into the temporary array, compacting it so it's still sorted--time is N.
  • For each element in the third array, search the temporary array; when you find a hit, stop. Time is less than N log N.

Here's code in Scala that illustrates this:

import java.util.Arrays

val a = Array(1,5,2,3,14,1,7)
val b = Array(3,9,14,4,2,2,4)
val c = Array(1,9,11,6,8,3,1)

Arrays.sort(a)
val count = new Array[Int](a.length)
for (i <- 0 until b.length) {
  val j =Arrays.binarySearch(a,b(i))
  if (j >= 0) count(j) += 1
}
var n = 0
for (i <- 0 until count.length) if (count(i)>0) { count(n) = a(i); n+= 1 }
for (i <- 0 until c.length) {
  if (Arrays.binarySearch(count,0,n,c(i))>=0) println(c(i))
}

With slightly more complexity, you can either use no extra space at the cost of being even more destructive of your original arrays, or you can avoid touching your original arrays at all at the cost of another N space.

Edit: * as the comments have pointed out, hash tables are faster for non-perverse inputs. This is "fastest worst case". The worst case may not be so unlikely unless you use a really good hashing algorithm, which may well eat up more time than your sort. For example, if you multiply all your values by 2^16, the trivial hashing (i.e. just use the bitmasked integer as an index) will collide every time on lists shorter than 64k....

Upvotes: 1

kennytm
kennytm

Reputation: 523334

Let N = 200, k = 3,

  1. Create a hash table H with capacity ≥ Nk.

  2. For each element X in array 1, set H[X] to 1.

  3. For each element Y in array 2, if Y is in H and H[Y] == 1, set H[Y] = 2.

  4. For each element Z in array 3, if Z is in H and H[Z] == 2, return Z.

  5. throw new InvalidDataGivenByInterviewerException();

O(Nk) time, O(Nk) space complexity.

Upvotes: 3

Nick Johnson
Nick Johnson

Reputation: 101149

Use a hashtable mapping objects to frequency counts. Iterate through all three lists, incrementing occurrence counts in the hashtable, until you encounter one with an occurrence count of 3. This is O(n), since no sorting is required. Example in Python:

def find_duplicates(*lists):
  num_lists = len(lists)
  counts = {}
  for l in lists:
    for i in l:
      counts[i] = counts.get(i, 0) + 1
      if counts[i] == num_lists:
        return i

Or an equivalent, using sets:

def find_duplicates(*lists):
  intersection = set(lists[0])
  for l in lists[1:]:
    intersection = intersection.intersect(set(l))
  return intersection.pop()

Upvotes: 2

IVlad
IVlad

Reputation: 43467

O(N) solution: use a hash table. H[i] = list of all integers in the three arrays that map to i.

For all H[i] > 1 check if three of its values are the same. If yes, you have your solution. You can do this check with the naive solution even, it should still be very fast, or you can sort those H[i] and then it becomes trivial.

If your numbers are relatively small, you can use H[i] = k if i appears k times in the three arrays, then the solution is the i for which H[i] = 3. If your numbers are huge, use a hash table though.

You can extend this to work even if you can have elements that can be common to only two arrays and also if you can have elements repeating elements in one of the arrays. It just becomes a bit more complicated, but you should be able to figure it out on your own.

Upvotes: 1

WannaBeGeek
WannaBeGeek

Reputation: 4076

Some improvement in Pelkonen's answer:
From converted problem in OP:

"Given that there is one and only one common element in these 3 arrays."

We need to sort only 2 arrays and find common element.

Upvotes: 5

Jacob
Jacob

Reputation: 34601

Use a hash table for each integer and encode the entries such that you know which array it's coming from - then check for the slot which has entries from all 3 arrays. O(n)

Upvotes: 2

Tuomas Pelkonen
Tuomas Pelkonen

Reputation: 7821

If you sort all the arrays first O(n log n) then it will be pretty easy to find the common element in less than O(n^3) time. You can for example use binary search after sorting them.

Upvotes: 5

Related Questions