Amazon Interview Question
Software Engineer / Developers1 2 3 4 5 6 7 sum 28
1 2 3 4 5 7 7 sum 29
difference = 1 repeated num = 7
abs(difference) - repeated number =6 doesnt exist in array so it is missing number
But this case?
1 2 3 4 sum 10
1 2 2 3 sum 8
difference = 2 repeated num = 2 abs(difference) + repeated nmber = 4 i think we can check abs(difference) - repeated number
int sum=0,sqsum=0;
for(int i=0;i<n;i++){
sum+=a[i];
sqsum+=sqsum+a[i]*a[i];
}
Now [n*(n+1)/2]-sum=Missing no - Repeated no
[n*(n+1)*(2n+1)/6]-sqsum=Missing no^2 - Repeated no^2...now solve for missing and repeated no:s and traverse the array to find out the ans...O(n) time O(1) space
Yes, indeed a great answer but you should be careful with the final formula.
Let dif = [n*(n+1)/2] - sum
Let DIF = [n*(n+1)*(2n+1)/6]-sqsum
If dif = 0, no number is missing.
Else
m-r = dif => r = m - dif
m^2-r^2 = DIF = m^2 - (m^2 - 2*m*dif + dif^2)=>
m = (DIF + dif^2)/(2*dif)
If the sign of DIF is 1, then the formula work fine.
Otherwise, the missing number will be -m. So, you will have to multiply it by -1 or call Abs(m).
The following algorithm has O(n) time complexity and O(1) space complexity. Let the number that was repeated be x and the number that was missed be y.
a) Since, n is given, we calculate sum of numbers, requiredsum = n(n+1)/2
b) We add all the numbers in the array to get givensum.
Now, requiredsum = givensum - x + y. Hence y - x = requiredsum - givensum.
c) Calculate the product of all numbers, requiredproduct = n!
d) Multiple all the elements in the array to get givenproduct which is (n! * x)/y
Now, (requiredproduct * x) / y = givenproduct. So, x = givenproduct * y / requiredproduct.
Substitute in original equation to get the value of y.
ya.. but you would need a special datatype or a BIG integer to store the product. Normal datatypes in (atleast C++) wont work with factorials greater than 171 (double in C++)
If no space issue, we can just use index array (say idx), initialize it to ZERO.
then for each element in array (Say a), increment index array. At the end, index with ZERO value is missing (And index with value 2 is repeated).
idx[n]={0};
for(i=0;i<n;i++)
idx[a[i]]++;
for(i=0;i<n;i++)
{
if(idx[i]==0) printf("%d is missing",i);
else if(idx[i]==2) printf("%d is repeated",i);
}
compute sum, y-x = sum - n*(n+1)/2
compute sum of squared y^2 - x^2 = sum of squared - n*(n+1)*(2*n+1)/6
from there you would know x and y
Let x be the missing number which is repeated and y be the repeated number.
If you XOR all the numbers int the array and subtract if from n(n+1)/2 you will get x+y
If you add all the numbers in the array and subtract if from n(n+1)/2 you will get x-y
Then solve the 2 simultaneous equations.
Let n=3
A[1,2,1]
1 is repeated twice and 3 is missing.
n(n+1)/2 = 6
XOR A =2
x+y=4
Solving we get both missing number and repeated number.
Add A = 4
x-y=2
I think Xor solution does not work.
Let's say
x is missing number and y is repeated number
and n = 5
Array is {1,2,3,4,4}.
Here x = 5, y = 4
Sum you have mentioned is = n(n+1)/2 = 15
Xor of all the numbers is (1^2^3^4^4) = 0
Difference between Sum and Xor is = 15 - 0 = 15 which is not equal to (x+y) i.e. (5 + 4) = 9
Hence your solution did not work.
We can use xor for this problem..
For eg:
let n be 3 and the given numbers be 1 2 2
Let y = (xor all the numbers from 1 to 3) xor (xor all the given numbers)
so y would be the missing number xor the repeated number (3 ^ 2)
let i be the last set bit in y
xor all the numbers from 1 to n and numbers in the given set whose ith bit is set. xor this number with y, this would give either missing number or duplicated. is the number we got here is not in the array then it is the missing number or this is the duplicated number. we get the missing number by xoring this number with y..
comments pls..
This solution does not work.
Lets say n = 5, Array = {1,2,3,4,4}
Xor from 1 to 5 = {1^2^3^4^5}
Xor of all given nos. = {1,2,3,4,4}
So y = 1^2^3^4^5^1^2^3^4^4 = 4^5 = Repeated ^ Missing.= 1
Last bit set in y(1) is 0th bit
Here xor all the numbers from 1 to n = {1^2^3^4^5}
and
numbers in the given set whose ith bit is set is = {1^3}
Thus whole Xor gives, {2^4^5}
Here, y is {4^5} and whole Xor {2^4^5}
Xoring above gives 2 which is neither missing nor repeated element.
Here's a O(n) without any extra space and without multiplication or addition (because factorial requires special datatype/datastructure)
// since we know there are n numbers in an array of size n all we want is to swap the numbers to their corresponding positions i.e. move '1' to 0th position, move '2' to 1st position ...etc.
if the number already exists in its position then its a duplicate and we set it to (n+1) or -1 i.e. something we can identify. Basically 2 traversals will give u the missing spot.
-> for(i=0;i<n;++i){
if(array[i]<0) //is less than zero only when we set the duplicate to -1, look below
continue;
if array[i]==i+1 //in the right position
continue;
else{
if(array[i]==array[array[i]-1]) //then its a duplicate, set it to -1
array[i] = -1
else
swap(array[i],array[array[i]-1])
}
}
//by the end of the above loop we have all elements in their corresponding positions and -1 in the place of the missing number
-> traverse the array and print out the position+1 of the the element with value == -1
//complexity analysis: no matter what the for loop will run 'n' times --> (n)
//traversal for finding the missing spot --> (n)
total complexity: O(n)
@Test public void findMissing()
{
int n=3;
int[] a=new int[n];
a[0]=2;a[1]=3;a[2]=3;
Hashtable m=new Hashtable();
for(int i=1;i<=n;i++)
{
m.put(i+"", i);
}
for(int i=0;i<a.length;i++)
{
if(m.containsKey(a[i]+""))
{
m.remove(a[i]+"");
}
}
//only one item left
System.out.println( m.values().iterator().next() );
}
#include <stdio.h>
#include <conio.h>
#define N 10
int main()
{
int a[10]={1,2,3,4,5,6,7,2,9,10};
int sumr=(N*(N+1))/2,sumi=0,rpt,sumdiff;
for(int i=0;i<N;i++)
{sumi=sumi+a[i];
for(int j=i+1;j<N;j++)
{if(a[i]==a[j])rpt=a[i];
}
}
sumdiff=sumr-sumi;
printf("%d",rpt+sumdiff);
getch();
return 0;
}
Suppose the given array is 1 2 3 3 5.
1. Compute sum of n numbers= n*(n+1)/2=15
2. Sum of this array=14
3. Sum of square of n numbers= n*(n+1)*(2n+1)/6=55
4. Sum of square for this array=48
5. Let a be the number repeated
Let b be the actual number
a-b=15-14=1
a (raised to power 2)- b (raised to power 2)=7
(a-b) * (a+b) = 7
a+b=7
a=4
b=3
Please comment if there is any flaw in this method.
int flag =0;
int count =1;
int missing_num;
int a[n]; //the array with n numbers
int main()
{
while(flag =0)
{
for(int i=1;i<=n;i++)
{
if(count==a[i])
{
count++;
flag=0;
break;
}
else
{
missing_num = count;
flag=1;
}
}
}
printf("The missing number is: %d",missing_num);
return 0;
}
Does this solution seem good?
Since the Question says that array contains only +ve numbers(and that too from 1 to N), we can use the original array itself to keep track of the numbers that have been visited. This can be done by making the entry at any index -ve whenever we encounter any element while traversing it. At the end values at all the indexes will be -ve except the missing number.
Time complexity: O(N)
Space Complexity: O(1)
Here is the C method to do the same:
Hope that helps!!!
- Guess who?? February 09, 2011