Interview Question
InternsCountry: India
Interview Type: In-Person
Nice idea, some modification:
x + y = Sum(A) - Sum(B)
x^2 + y^2 = Sum(A[i]^2) - Sum(B[i]^2)
Solve the equations to find x and y.
Instead of doing sum(a)-sum(b) ou can do sum(a[i]-b[i]) for i:0>n. The same for mul/mul. This way you avoid (in general)having a too large sum/mul number
For small integers array and small number of elements, sum/mul solution works pretty good.
But:
1) what if the you have lots of elements and the numbers are big, we will get overflow error
2) what if we canot apply sum/mul operations to the elements in the input arrays? For example, the array has some file names instead of integers.
proposed solution:
1) sort both array, and scan through to compare two arrays.
O(nlogn) time complexity.
Solution using difference of sum is nice but as pointed by samuel: what if the you have lots of elements and the numbers are big, we will get overflow error
proposed solution is:
1) Create a HashMap<K, V> where K = number and V = count occurences of number
2) loop through both arrays at the same time adding values and counts to Map
3) iterate over HashMap and print those elements where count = 1
Implementation in Java:
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static void printMissingElems(int[] a, int[] b) {
Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();
int i = 0;
int aLen = a.length;
int bLen = b.length;
int lenBiggest = aLen > bLen ? aLen : bLen;
while (i < lenBiggest) {
if (i < aLen) {
addNum(mapCount, a[i]);
}
if (i < bLen) {
addNum(mapCount, b[i]);
}
i++;
}
printDiffNums(mapCount);
}
public static void printDiffNums(Map<Integer, Integer> mapCount) {
for(Map.Entry<Integer, Integer> entry : mapCount.entrySet()){
if (entry.getValue() == 1) {
System.out.println(entry.getKey());
}
}
}
public static void addNum(Map<Integer, Integer> mapCount, int num) {
if (!mapCount.containsKey(num)) {
mapCount.put(num, 1);
} else {
int count = mapCount.get(num);
mapCount.put(num, count + 1);
}
}
public static void runSampleTests() {
int[] a = {1, 4, 8, 3, 15, 33, 92, 145, 25, 22, 29, 38, 73, 66, 71};
int[] b = {1, 4, 8, 3, 15, 19, 33, 92, 145, 25, 22, 29, 38, 44, 73, 66, 71};
printMissingElems(a, b);
}
public static void main(String args[]) {
runSampleTests();
}
}
O(N) time and O(N) space solution.
Let s1 has n+2 elements and s2 has n elements. We want to find two missing elements in s2.
[Step 1] Compute sum(s1) and sum(s2); while computing sum(s2) simultaneously build up a set(s2) from the elements in s2.
[Step 2] Compute sum_diff = sum(s1) - sum(s2)
[Step 3] Go through each element in s1, see if that number appears in the set(s2). If not, that element and sum_diff-element are the missing pair
void find_missing_pair(vector<int>& s1, vector<int>& s2)
{
int sum_s1=0, sum_s2=0, sum_diff=0;
for(int i=0; i<s1.size(); i++)
sum_s1 += s1[i];
unordered_set<int> set_s2;
for(int i=0; i<s2.size(); i++) {
set_s2.insert(s2[i]);
sum_s2 += s2[i];
}
sum_diff = sum_s1 - sum_s2;
for(int i=0; i<s1.size(); i++) {
if( set_s2.find(s1[i])==set_s2.end() ) {
printf("%d and %d missing!\n", s1[i], sum_diff-s1[i]);
return;
}
}
}
I think that the time complexity of this solution is O(n^2) as set_s2.find() method takes O(n) time to search the element.
Let Array A contain n elements
Let Array B contain n+2 elements
1. Find Sum(A) ==> O(N)
2. Find Sum(B) ==> O(N)
3. Sum(B) - Sum(A) ==> Gives u sum of the two missing numbers
4. Sort Array B ==> O(NlogN)
5. Use the algorithm to find pair of integers from sorted Array B that add up to difference in step 3 ==> O(N)
Complexity 3N + NlogN
Solution in C++ (linear time) :
void printElements(vector<int> L1, vector<int> L2) {
// Assumes L1 is the list with two additional elements
int xored1 = 0, xored2 = 0,
summed1 = 0, summed2 = 0;
vector<int>::iterator it;
for (it = L1.begin(); it != L1.end(); ++it) {
xored1 ^= *it;
summed1 += *it;
}
for (it = L2.begin(); it != L2.end(); ++it) {
xored2 ^= *it;
summed2 += *it;
}
int a, b;
if ((xored1 ^ xored2) == 0) {
a = (summed1 - summed2) / 2;
b = a;
} else {
int i = 0;
while ((xored1 ^ xored2) >> (i + 1)) {
++i;
}
xored1 = 0;
xored2 = 0;
for (it = L1.begin(); it != L1.end(); ++it) {
if (*it & (1 << i))
xored1 ^= *it;
}
for (it = L2.begin(); it != L2.end(); ++it) {
if (*it & (1 << i))
xored2 ^= *it;
}
a = xored1 ^ xored2;
b = summed1 - summed2 - a;
}
cout << a << "," << b << endl;
}
Sure, it uses the fact that a^(a^b) = b.
We have xored1 which is the xor of all the elements in first list (with the 2 extra elements) and xored2 the same for the second list. We also have both sums of the lists.
Then xored1 ^ xored2 = x1^x2 where x1,x2 are the extra elements. If this equals zero, it means that the two extra elements are the same, hence are equal to the difference between the two sums divided by 2.
Otherwise, it means that the 2 elements are different in a least one bit. We compute position i of the first different bit. We then take all elements in both list where the bit at position i is 1. There is exactly one element different between those two sublists which we can find easily. We deduce the other element from that and we are done.
public class FindTwoExtraNumbers {
public static void findExtras(int[] a, int[] b) {
int xor = 0;
for (int i : a) {
xor ^= i;
}
for (int i : b) {
xor ^= i;
}
// Let x and y be the two extras
int x = 0, y = 0;
// Create a mask containing one of orx's 1 bit. For convenience,
// the right most 1 bit is used here.
int mask = xor & ~(xor - 1);
// Go through all elements of the two arrays, and xor them to
// either x or y, depending on their corresponding bit's value.
for (int i : a) {
if ((i & mask) != 0)
x ^= i;
else
y ^= i;
}
for (int i : b) {
if ((i & mask) != 0)
x ^= i;
else
y ^= i;
}
System.out.println(x + " and " + y);
}
public static void main(String[] args) {
int[] a = { 3, 25, 27, 54, 55, 62, 68, 85, 94, 95 };
int[] b = { 3, 8, 25, 27, 54, 55, 61, 62, 68, 85, 94, 95 };
findExtras(a, b);
}
}
public class FindTwoExtraNumbers {
public static void findExtras(int[] a, int[] b) {
int xor = 0;
for (int i : a) {
xor ^= i;
}
for (int i : b) {
xor ^= i;
}
int x = 0, y = 0;
// mask containing the right most set bit in the xor.
int mask = xor & ~(xor - 1);
// Go through all elements of the two arrays, and xor them to
// either x or y, depending on their corresponding bit's value.
for (int i : a) {
if ((i & mask) != 0)
x ^= i;
else
y ^= i;
}
for (int i : b) {
if ((i & mask) != 0)
x ^= i;
else
y ^= i;
}
System.out.println(x + " and " + y);
}
public static void main(String[] args) {
int[] a = { 3, 25, 27, 54, 55, 62, 68, 85, 94, 95 };
int[] b = { 3, 8, 25, 27, 54, 55, 61, 62, 68, 85, 94, 95 };
findExtras(a, b);
}
}
1) Use Hashset and all all values from A and B to it in a way:
a) If already present: delete
b) else add
2) If Hashset is non-empty, it will essentially contain two numbers. These are the two numbers that we are looking for.
2) If Hashset is empty, this means that the two numbers are the same. We can find out these numbers by subtracting the sums of the two arrays A and B and dividing the difference by 2.
Solution in Java(N log N)
public class FindMissingElements {
private static void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
/* This function takes last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right of pivot */
private static int partition (int arr[], int l, int h)
{
int x = arr[h]; // pivot
int i = (l - 1); // Index of smaller element
for (int j = l; j <= h- 1; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= x)
{
i++; // increment index of smaller element
swap(arr, i , j); // Swap current element with index
}
}
swap(arr, i+1, h);
return (i + 1);
}
/* arr[] --> Array to be sorted, l --> Starting index, h --> Ending index */
private static void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int p = partition(arr, l, h); /* Partitioning index */
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}
private static int findOneNumber(int[] a, int[] b) {
int x = 0;
int len = 0;
int i = 0;
if(a.length > b.length) {
len = b.length;
while(len > i) {
if(a[i] != b[i])
return a[i];
i++;
}
if(len == i) return a[len];
} else {
len = a.length;
while(len > i) {
if(a[i] != b[i])
return b[i];
i++;
}
if(len == i) return b[len];
}
return x;
}
private static int findOtherNumber(int[] a, int[] b, int oneNumber) {
int sumA = 0, sumB = 0, diff = 0;
for(int i = 0 ; i < a.length ; i++)
sumA += a[i];
for(int i = 0 ; i < b.length ; i++)
sumB += b[i];
diff = sumA - sumB;
if(diff > 0) {
return diff - oneNumber;
} else {
return -1 * diff - oneNumber;
}
}
public static void main(String[] args) {
int[] a = {1, 6, 8, 3, 16, 33, 192, 145, 25, 28, 29, 38, 73, 66, 71};
int[] b = {1, 6, 8, 3, 16, 19, 33, 192, 145, 25, 28, 29, 38, 44, 73, 66, 71};
int lenA = a.length;
int lenB = b.length;
quickSort(a, 0, lenA - 1);
quickSort(b, 0, lenB - 1);
int oneNumber = findOneNumber(a, b);
int otherNumber = findOtherNumber(a, b, oneNumber);
System.out.println(oneNumber + ", " + otherNumber);
}
}
If there are any error or improvement, please let me know.
this could also be an answer:
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
main()
{
//a[5], b[3];
int c,x,d,z,k[2],n1,n2,a[10],b[12];
printf("\nsize of array1\n");
scanf("%d",&n1);
printf("\nsize of array2\n");
scanf("%d",&n2);
printf("\nenter array 1\n");
for(c=0;c<n1;c++)
{
scanf("%d",&a[c]);
}
printf("\nenter array 2\n");
for(c=0;c<n2;c++)
{
scanf("%d",&b[c]);
}
for(c=0;c<n1;c++)
{
d=a[c];
for(x=0;x<n2;x++)
{
z=-1;
if(b[x]==d)
{
z=0;
break;
//continue;
}
else
{
z=d;
//printf("\n%d\n",z);
}
}
if(z!=0)
printf("\n%d\n",a[c]);
}
getch();
}
Let's say |A| = n+2 and |B| = n, and element to find are x,y
- RG February 15, 2014x+y = sum(A)-sum(B);
x*y = mul(A)/mul(B);
(x+y)^2 = x^2 + y^2 +2xy
Then find x,y