Amazon Interview Question
Country: United States
Since quickest way is asked, why not just make a hash table(summing all the given nos and their squares will take time)?
I found a similar question on stack overflow:
stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe
We can solve Q2 by summing both the numbers themselves, and the squares of the numbers.
We can then reduce the problem to
k1 + k2 = x
k1^2 + k2^2 = y
Where x and y are how far the sums are below the expected values.
Substituting gives us:
(x-k2)^2 + k2^2 = y
Which we can then solve to determine our missing numbers.
Example:
NumN: 1, 2, 3, 4, 5
Let's say 3 & 4 are missing (x and y)
ListN : 1, 2, 5
x + y = 7 -- (1) // SumOfNumN - SumOfListN
x^2 + y^2 = 25 -- (2) // (sumOf the squares in NumN) - (sumOf the squares in ListN)
Substitute (1) in (2),
x^2 + (7 - x)^2 = 25
Roots: 3, 4 which are the missing numbers
Not really.
My answer was: Assign each number to a treemap slot, iterate through the treemap using "iter" and simultaneously have counter from 0. If [iter.next() != counter]. Print that number as missing and do an ++counter if you find counter==inter.Next() else dont increment.
List<int> numbers = new List<int>();
//populate with the missing numbers
//etc
Treemap<int,int> treenum = new Treemap<int,int> ();
for(int num : numbers)
{
treenum.put(num,1);
}
int counter=0;
for(Entry<int,int> entry : numbers.entrySet()){
if(entry.getKey() == counter) {
counter++;
continue;
}
logger(Missing number is: counter;)
//Dont increment counter now
}
Is there a clever way of not using any sort of mapping?
This problem is trivial when the list is sorted, so let's assume it's not. Even for an unsorted list, it's trivial to solve in linear time, so it's not worthwhile to sort the list first.
When only one number is missing, you can compute the sum of the list and compare it to the sum of the first N integers (N*(N+1)/2), and the difference is the missing number. If more than one number is missing, then the clever trick doesn't help a whole lot, since there are multiple pairs of numbers that could account for the shortage.
So, without clever tricks, let's eliminate fancy data structures too. Just allocate an array of N booleans, and set them all to false. In your first pass, go through the input array, take the number and set the array of booleans to false for that index. Then, in a second pass, iterate through your array of booleans to find which numbers were left out.
Overall running time is O(N), and because you're not using a fancy data structure like a hash or a tree, it's reliably linear, even for a worst case ordering.
My pet peeve is you are still using some sort of a data structures to set/unset the boolean values. It's nothing but mapping.
@xankar, agreed. My comment was mostly directed at the treemap solution, which is neither simple or clever. If you're gonna use a map, then you should take advantage of the main constraint--all integers from 1 to N--and implement your map as a simple array of booleans, or, better yet, a bitmap.
Other folks have since posted the clever solution. Sum the numbers, and sum the squares of the numbers, find the shortages in both, then use simple algebra to deduce the two missing values. It's kind of a parlor trick, but I would definitely be thrilled if an interview candidate knew it.
The way of summing the numbers proposed by @debayan is great,but it is not the quickest way.There is a better approach using xor tricks.
1).xor all the elements with number 1-N, then the result be would be:
b = miss1 ^ miss2
2).as miss1 and miss2 are different numbers, they are at least different at 1 bit of their binary reprentations,take 2(0x0010) and 3(0x0011) for example,they are different at the first bit(count form right to left).So we can use one bit that miss1 and miss2 are different at to divide the array a into 2 parts,for array {1 2 4 5 7 8},b is 5, we use the first bit of b to divide array a,then we would get two subarray:{1 5 7},{2 4 8}
3)after step 1) and 2) ,this problem becomes similar to the problem of finding the only one missing number in array of elements 1-N
time complexity:O(n)
space complexity:O(1)
below are the C++ code
void Find2MissingNums(int a[],int n)
{
int b = ((n+1)^(n+2));
for(int i=0;i<n;i++)
b ^= (a[i] ^ (i+1) );
int mask = 0x01;
while(!(b & mask))
mask <<= 1;
int miss1 = 0;
int miss2 = 0;
for(int i = 0;i<n;i++)
{
if(a[i] & mask)miss1 ^= a[i];
else miss2 ^= a[i];
if((i+1) & mask)miss1 ^= (i+1);
else miss2 ^= (i+1);
}
if((n+1) & mask)miss1 ^= (n+1);
else miss2 ^= (n+1);
if((n+2) & mask)miss1 ^= (n+2);
else miss2 ^= (n+2);
cout<<miss1<<" "<<miss2<<endl;
}
test cases:
{1,2,4,5,6,8}; 7 3
{1,3,4,5,7,8}; 6 2
{1,2,3,4,5,6}; 7 8
{3,4}; 1 2
@duckling - Nice solution. But would you please clarify the reason behind the initialization of b as "b = ((n+1)^(n+2))" .. everything else follows fine..
@ss .the elements are between 1 to N,and two of them are missing,so N = n+2,where n is the total number of elements now,we have to xor all the elements with number 1 to N ,so initially, we set b to (n+1)xor(n+2),and then xor with 1 to n and a[i ... n] .
i have changed 'n' to 'N' in my explanation,
take {1 2 4 5 7 8} for example ,the xor result b is 5(0101),we find that miss1 and miss2 different at the first bit(also different at the third bit),we then use this one bit to divide the array to two parts, then we will get two sub-array {1 5 7},{2 4 8}(note that we don't really need to divide the elements into two parts,we just need to check their values at that bit ).
now this problem can be reduced to the problem of finding the only one missing number in array {1 5 7} that elements are either{1 3 5 7} and the only one missing number in array { 2 4 8} that elements are either {2 4 6 8}, i think you should know to how solve this simpler problem.
Use XOR operation.
XOR numbers 1 to N and the given list of numbers.
The resultant will contain the bits set on only in either of the missing numbers.
Consider the position of set bit. Need to do only once. Divide the numbers 1 to N in two groups, one which contains that bit set and one group which doesn't have one bit set. Similarly, divide the given numbers among those groups.
XOR the groups to get the numbers.
XOR of first group will result to first missing number and XOR of second group will result to second missing number.
Concept:
A^A = 0;
I got a solution using only xor operation.If we do little modification then the Question is same as, A array is given having all the numbers repeated even times except 2 number which is repeated odd no of times then find the no??
#include <stdio.h>
int main()
{
int arr[]={1,3,4,5,6,7,8,9,10,11,13};
int lenofArr = sizeof(arr)/sizeof(arr[0]);
int i=0,j=0, from=1, to=13;
int xorResult=0, firstNo=0, secondNo=0, setBit=0;
for(i; i<lenofArr; i++)
xorResult ^= arr[i];
for(i=1; i<= to; i++)
xorResult ^= i;
int backupResult=xorResult;
while(! (backupResult & 1 ))
{
backupResult >>=1;
setBit++;
}
firstNo = secondNo = xorResult;
for(i=0; i<lenofArr; i++)
{
if( (arr[i]>>setBit) & 1)
firstNo = firstNo^arr[i];
else
secondNo = secondNo^arr[i];
}
for(i=from; i<= to; i++)
{
if((i>>setBit) & 1)
firstNo = firstNo^i;
else
secondNo = secondNo^i;
}
printf("the first No is %d", firstNo);
printf("\nthe second no is %d ", secondNo);
return 0;
}
let say x, y are the two elements missing...
we know that
sum(1..N) = sum(1.x..y...N);
so
x+y = sum(1..N) - sumExcludingX&Y(1..N)
x+y = constant;
similarly we can divide all the elements..
multiply(1..N) / multiply(1.x..y.N) = 1;
so
x.y = constant;
solve the above two.. you will get x & y..
The algorithm takes (n).. with a constant space..
Professional opinion-Generally if the array is unsorted, the most efficient algorithm must be O(n),
First method is calculate the: x+y=c and x.y=d and then figure out x,y just described above.
this needs O(n) time but problem is if N is very large, it must be overflow!!!
Second method is use hash table, build a hash table use array(1,N) and scan from 1.....N to figure out the missing number. Time complexity O(n), space O(n)
Yep, I would only go the fancy solution if space was severely constrained. Overflow's a fiddly issue, but it's relatively straightforward to manage big integers with a simple multi-byte integer class, since sums and squares are pretty straightforward.
Why use a hash map instead of a bit vector or simple array of booleans? You know that the numbers range from 1 to N and are unique. Why pay the price of collisions in a hash table?
// I know it might take more time and is less fancy than the examples above but
// couldn't you just create some form of tally array?
int[] arr = {1, 2, 3, 4, 5, 8, 9}; // 6 & 7 are missing
int[] tally = new int[arr.length + 2]; // create tally array
for(int i = 0; i < arr.length; i++)
{
tally[arr[i] - 1]++; // increment value of tally at the index of the arr[] - 1
}
int num1 = 0, num2 = 0;
for(int i = 0; i < tally.length; i++)
{
if(tally[i] == 0 && num1 == 0)
{
num1 = i + 1;
}
else if(tally[i] == 0 && num2 == 0)
{
num2 = i + 1;
}
}
If it is a sorted one,
findMissingNumbers(int[] array,int n){
int k=0;
for(int i=1;i<=n;i++){
if(array[k]!=i) System.out.println(i);
else k++;
}
}
It is of linear time only. If the missing number is one instead of two then by modifying binary search we can find it in logarithmic time. But I am certain that I am missing something here. If it was the the same question as I thought, It would've solved a long time back. can anyone let me know if I didn't get the question properly.
#include<stdio.h>
#include<malloc.h>
int main() {
int *a,n,i,count=0,flag=0;
printf("Enter values of N\n");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
for(i=0;i<n;i++) {
printf("Enter the series\n");
scanf("%d",&a[i]); }
printf("The series is\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
if(a[0]!=1) {
printf("1st number missing\n");
count++; }
if(a[n-1]!=n) {
flag=1;
count++; }
for(i=1;i<n/2 && count<2;i++) {
if(a[i]!=a[i-1]+1) {
printf("%d th number missing\n",i+1);
count++;
if(count<2)
a[i]=a[i-1]+1; }
if(count==2)
break;
if(a[n-i-1]!=a[n-i]-1) {
printf("%d th number missing\n",n-i);
count++;
if(count<2)
a[n-i-1]=a[n-i]-1; }}
if(flag==1)
printf("last number missing\n");
return 0;}
suppose we have numbers 1-5:
array looks like : arr = { 1 ,3 ,3 ,1 ,5 }(numbers 2 and 4 are missing)
1 : iterate through the array :
for index i , make arr[i-1] = -1*arr[i] if arr[i-1] is not negative
so the array will look like : -1 3 -3 1 -5
2 : again iterate through the array, the indices that have positive numbers + 1 is the
answer , in this case 2 and 4
I didnt get the logic of your algorithm. Can you be more specifi why you making arr[i-1] negative?
As we know that numbers are from 1-N we can use same array check whether some index is visited or not.
in the example that i gave numbers 2 and 4 we absent
so arr[1] and arr[3] will always remain positive as we never encounter 2 and 4.
As we are getting numbers 1,3,5 indices 0,2,4 will become negative.
like this : -1 3 -3 1 -5
the positive indices +1 is the answer.
I have done arr[i-1] because I have assumed that indices start from 0.
use XOR
def missingTwoNumber(array,n):
a = reduce(numxor,range(1,n+1))
b = reduce(numxor,array)
c = a ^ b
d = 0
while True:
if (1 << d) & c != 0:
break;
else:
d += 1
print c
range1 = filter(lambda x:(1 << d) & x != 0,range(1,n+1))
print range1
range2 = filter(lambda x:(1 << d) & x == 0,range(1,n+1))
print range2
array1 = filter(lambda x:(1 << d) & x != 0,array)
print array1
array2 = filter(lambda x:(1 << d) & x == 0,array)
print array2
a1 = reduce(numxor,range1)
a2 = reduce(numxor,range2)
b1 = reduce(numxor,array1)
b2 = reduce(numxor,array2)
print a1 ^ b1
print a2 ^ b2
def numxor(x,y):
return x^y
missingTwoNumber([1,2,4,5,7,8],8)
Generalizing to k missing numbers. Single pass thru the array with XOR method.
public class Missing {
public static void main(String[] args) {
int jump = 0, missing=0;
byte[] arr = {2,3,6,7,8,10,11,20};
for (byte i = 0; i < arr.length; i++){
int res = arr[i] ^ (i+1+missing);
if (res!=0) {
jump = arr[i] - (i+1+missing);
for (int j= jump; j>=1; j--)
System.out.println("Missing:"+(arr[i]-j));
missing+=jump;
}
}
}
}
Time Complexity O(n) space complexity O(1)
public static void findMissingElementsInSeriese(int[] inputarray) {
boolean isfound = false;
for (int i = 0, k = 0; i < inputarray.length; i++) {
if (inputarray[i] != i + k + 1) {
System.out.println((i + k + 1));
k++;
isfound = true;
}
}
if (!isfound) {
System.out.println("No missing elements found");
}
}
compute 1 ) sum of 1-n sum = a + b
- debayan March 16, 20132 ) sq of sum of 1- n . sum_sq = a^2 + b^2
O(n)
compute sum of input numbers in array
sum1 = a + b
sum_sq1 = a^2 + b ^2
O(n)
sum - sum1 = sum of missing two numbers say (x + y )
sum_sq - sum_sq1 = x^2 + y^2
now : xy = ((x+y) ^ 2 - (a^2 + b^2)) / 2
so , x- y = sq (( x-y)^2) = sq ((x+y)^2) -4xy )
once we get x-y and x+y we can solve and get two number value .
this is the quickest way .
correct me if i am wrong