Amazon Interview Question
Testing / Quality AssurancesPlease check my code:
#include<stdio.h>
int findmissing(int a[],int n)
{
int i=0,s=0;
for(i=0;i<n-1;i++)
{
s = s^a[i]^(i+1);
}
s = s^n;
return s;
}
int main()
{
int a[]={5,4,1,3};
printf(" %d ",findmissing(a,5));
return 0;
}
Feedbacks are welcome.
What if an element is missing and instead we have a duplicate value. In that case your sol doesn't work.
Thats Correct ... I assumed missing slot would have 0.
Then solution would require detecting duplicate value. Another array of size 100 can be used ... traverse first array and use values as indices for the other array and mark those slots. If we encounter already marked slot, duplicate is found. Using this value and difference above, missing value can be detected.
missing value = duplicate value + difference
Solution looks a bit inefficient ... any suggestions?
yes, it could be any range of width 100, in which case i guess we would have to take the minimum value in the original array (found in O(n) time), and use it as an offset to subtract from the value to obtain the corresponding index in the array C mentioned above. so for the range 321-420, the value 400 would correspond to index 400-321 = 79.
The above solutions require another array of equal size. Suppose we could modify the array. Just need to perform a sort and find the duplicate value using two pointers.
Would turn out to be O(nlog n) though.(Assuming we use quick sort or merge sort.
hi we can do this using xor,
for(i=0; i < 100;i++)
num = num ^ array[i] ^ (i+1);
after this num = xor of all array values and numbers from 1 to 100
xor of duplicate numbers becomes zero so
so num becomes duplicatenumber ^ 100
so now xor the num with 100 we will get duplicate number.
num = num ^ 100;
so num is the required output.
man..this is just an array of fixed numbers so we can sort it in O(n) and with no extra memory and then the problem is solved....
In case say x is the missing element and is in turn replaced by y (for say numbers in the range 1 to N)
Let A be the original series from 1 to N
Let B be the series as described above
Summation(A) - Summation(B) = y-x
Product(A) / Product(B) = x/y
Based on these 2 equations, you can obtain x and y (the missing and the duplicate element respectively)
the array can be sorted in O(n) for consecutive 100 numbers. ie; start scanning from start.take the number at first position and swap number with the element at corresponsing index.if number at first position is 55.and number at 55th position in 76. then swap 55 and 76.this way we send the number to the index of same value.one scan and array is sorted.once sorted one more scan to compare adjacent numbers to give missing one
Insted of calculating
1*2*....*100
we can calculate 1*1+2*2... 100*100
because
n! > 1*1+2*2 ....n*n for n>4
so n! will take data type with larger range
so we have
s1=SUM(A*A)-SUM(B*B)=x*x-y*y=(x-y)(x+y)..1
and
s2=SUM(A)-SUM(B)=(x-y) ..2
dividing 1 by 2 we have
x+y= s1/s2 ..3
by 2 & 3rd eqution we find x and y
If missing number is not filled as zero and some other number is duplicated then:
let the missing number be x
let the duplicated number be y
Existing product = P1
Actual product of N numbers = P2
Both these products have atleast a component common which is the product of the remaining n-1 numbers say that is P
therefore P1 = P * x
and P2 = P * y
here P is the GCD of P1 and P2.
Thus find the GCD of P1 and P2 and divide P1 and p2 by it and get x and y.
If the missing number is replaced by zero then P2 would be zero. In that case use the summation method discussed above
ENJOY!!!
Assumption : Array starts from 1 else find the min and work acc.
int[] a = {1,2,3,3,5};
int sum = 0;
int prodsum = 0;
int actualsum = 0;
int actualprodsum = 0;
for (int i =0; i< a.length; i++)
{
sum = sum + a[i];
prodsum = prodsum + (a[i] * a[i]);
int j = i+ 1;
actualsum = actualsum + j;
actualprodsum = actualprodsum + (j * j);
}
int repeated = 0;
int missing = 0;
if(sum != actualsum)
{
int m = sum - actualsum;
repeated= ((prodsum - actualprodsum) + (m * m))/(2*m) ;
missing = actualsum - sum + repeated ;
}
the problem explicitly says "all numbers between 1 and 100 except one missing" in an array of length 99. How can we have duplicated numbers? How can the numbers be some other consecutive numbers?@_@
Thank you, Chaos, for for the moment of clarity. I was going to point out the same comment until I saw yours.
Many of the responses above make me want to point out something crucial in any engineering environment... before you answer a question, make sure you understand the problem and all the information you have.
"all the numbers between 1 and 100, except for one number that has been removed"
Sort the array then Iterate through, subtracting each element from the previous element, testing the difference. When the difference == 2, return the current minuend-1
This works for arrays of n size.
There are probably more elegant ways to do it, but the problem states a 99-element array which is so small that it renders performance considerations negligible.
Here's the implementation in Ruby (and why I love Ruby ):)
#!/usr/bin/env ruby
#create array
complete_array=*(1..100)
element_to_remove = rand(max=100)
incomplete_array = complete_array
incomplete_array.delete(element_to_remove)
#Find missing value
last = 0
incomplete_array.sort.each do |value|
diff = value - last
if diff == 2
puts value-1
else
last = value
end
end
One of the easiest approaches to the above problem is to use the XOR operator to find out the missing number in the array from 1 to any number (here 100), taking XOR will lead to the elimination of the repeated integers which are present in the array and from 1 to n, thus printing the result.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findfirstrepeatedelement(int arr[], int n){
int x1 = arr[0];
int x2 = 1;
for(int i = 1; i < n; i++)
x1 = x1 ^ arr[i];
for(int i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
int main()
{
int a[] = {1, 2, 4, 5, 6};
int miss = findfirstrepeatedelement(a, 5);
cout << miss;
return 0;
}
For solving the above algorithm we need to first take the xor of all the numbers from 1 to 100 and then take the xor of all the array elements and then at the end collectively take the xor of both the numbers.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int findmissing(int arr[]){
int array_xor = arr[0];
int number_xor = 1;
for(int i = 2; i <= 100; i++)
number_xor = number_xor ^ i;
for(int i = 1; i < 100; i++)
array_xor = array_xor ^ arr[i];
return number_xor ^ array_xor;
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100};
cout<<findmissing(arr)<<endl;
return 0;
}
"Missing" word indicates that the array has numbers from 1 to 100 (which may be out of sequence though). Add all the elements in the array and subtract the sum from 5050.
- Prakash January 29, 2006(100 * 101)/2 = 5050