## Amazon Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
9
of 11 vote

compute 1 ) sum of 1-n sum = a + b
2 ) 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

Comment hidden because of low score. Click to expand.
1
of 1 vote

Your code may suffer from overflow problem. How You will handle such problem??

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

@ADi .. it should not fail .. can u pls xplain with an example and dry run ..

Comment hidden because of low score. Click to expand.
0

Since quickest way is asked, why not just make a hash table(summing all the given nos and their squares will take time)?

Comment hidden because of low score. Click to expand.
0

Solving in O(n) in easy . Is it possible to solve in O(logn)

Comment hidden because of low score. Click to expand.
0

what a fab solution!!!

Comment hidden because of low score. Click to expand.
0

I think we can add base cases before solving the above equation.
like if actualsum and expectedsum are equal then missing numbers are N+1 and N+2,
if (expectedsum - actualsum)^2 =(expectedsumsq - actualsumsq)
then missing number are expectedsum - actualsum and N+1.

Comment hidden because of low score. Click to expand.
3
of 5 vote

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``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Is the series sorted?

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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 miss1 = 0;
int miss2 = 0;
for(int i = 0;i<n;i++)
{
else miss2 ^= a[i];
else miss2 ^= (i+1);
}
else miss2 ^= (n+1);
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``````

Comment hidden because of low score. Click to expand.
0

@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..

Comment hidden because of low score. Click to expand.
0

@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,

Comment hidden because of low score. Click to expand.
0

Solving in O(n) in easy . Is it possible to solve in O(logn).

Comment hidden because of low score. Click to expand.
0

can you please explain what is the second for loop doing??thanks..!!

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

Comment hidden because of low score. Click to expand.
0

Simple example pls

Comment hidden because of low score. Click to expand.
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);
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;
}``````

Comment hidden because of low score. Click to expand.
0

The problem with an XOR solution for the two-numbers-missing problem is that 1 xor 2 is the same as 5 xor 6 and 13 xor 14. It's not clear to me that you've actually resolved that conundrum. Maybe show some tests?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// 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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.``````

Comment hidden because of low score. Click to expand.
0

Please Ignore this solution. I was completely missing it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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!=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;}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I didnt get the logic of your algorithm. Can you be more specifi why you making arr[i-1] negative?

Comment hidden because of low score. Click to expand.
0

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 and arr 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.

Comment hidden because of low score. Click to expand.
0

sorry for the mistake, instead of
" make arr[i-1] = -1*arr[i] if arr[i-1] is not negative "
it should be
" make arr[ arr[i] -1 ] = -1*arr[ arr[i] -1 ] , if arr[i-1] is not negative "

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solving in O(n) in easy . Is it possible to solve in O(logn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

great

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

instead of 2 missing we can also solve k missing elements according to the link ..

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.