Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
One possible solution is the sum solution which was already suggested. The problem with this solution is that for a general n (n=100 in the original problem), calculating the sum may cause overflow (for example n > sqrt(Integer.MAX_VALUE)).
Another solution is to use the xor operator. Recall that xor is commutative, associative and also satisfies the following:
1. a xor a = 0
2. 0 xor a = a
Using these observation, it's easy to see the following:
missing_element = 1 xor 2 xor ... xor n xor arr[0] xor arr[1] xor ... xor arr[n-2] (the array has n-1 elements).
public static int findMissing(int[] arr) throws NullPointerException {
if (arr==null){throw new NullPointerException();}
int res = 0;
for (int i=0;i<arr.length;i++){res^=arr[i]^(i+1);}
res^=(arr.length+1);
return res;
}
This is really interesting! To the question above, you'll be xoring every number in the array as well as every index in the array.
Eg if the missing element is 4, you'll be evaluating the expression that includes 2 copies of each number except 4,of which there will be only one.
That is, (a xor a) xor (b xor b) xor (c xor c)... xor MISSING_NUMBER. This is equivalent to 0 xor 0 xor 0...xor MISSING_NUMBER, Which is equivalent to the missing number itself.
Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same.
@ZSGoldberg "Obviously this solution also fails if there are duplicates in the array, we would have to know that the set of indices and set of values are the same."
You are right about solution failing for duplicates in array.
But we do not necessary need to know that set of indices and set of values are same. So 1 xor 20 xor 1 will still give you 20, since xor is associative, no order needed be maintained like 1 xor 1 xor 2 xor 2 .... etc.
Hope that's clear?
@Roxanne - yep! Tried to capture that by saying the "the set of" indices and "the set of values" are the same. 'Sets' being lists not in any particular order
This solution works great if there are no duplicate values in the array.
example:
if we have missing element 5 and 4 occur twice then result has to be 5 (as expected)
but it will be 4(from array) XOR 4 (from array) XOR 4 (from Index) XOR 5 (from Index)
Now result will be from = 4 (from Index) XOR 5 (from Index) .. as both 4 from array will cancel mutual effect.
to solve this situation we can take one more array of bool(Occupancy Array). What ever value we get from array we go to that
index of occupancy array and mark it as occupied (true). After traversal of all value ... we traverse this occupancy array ...
the index which has false value will be our result.
it mean we have an array with 98 elements; and every cell has a unique value from 1 to 100
1. sort array
2. apply binary search to go over array and cheek values. So, array[49] must be equal to 50, if it 's 49 - then check left part, it it's 50 - check right part
The solution suggested above:
(Sum of natural number from 1 to 100) - (sum of all the elements present in the given array) will give the missing number and infact smart way too :)
I can also think of another solution just let me know if this is efficient enough or not :
Sort the array in increasing order(if not already given in sorted fashion). Then the difference of any two consecutive number should be 1, wherever its not that is our culprit .
Java code for the same:
public class FindMissing {
public static void main(String[] args) {
int array[] = { here sorted input array will come};
for(int i = 0; i<array.length-1; i++){
if(array[i+1]-array[i] !=1)
System.out.println("The missing number is: " + (array[i] + 1));
}
}
}
int[] dizi = new int[100];
for (int i = 1; i < 101; i++)
{
dizi[i-1] = i;
}
//dizi[69]=70
//delete it from array to see is it working
dizi[69] = 0;
for (int i = 1; i < 100; i++)
{
if (dizi[i]-dizi[i-1]!=1)
{
Console.WriteLine(i+1);
break;
}
}
Console.ReadLine();
it works
1. First sum up all numbers from 1 thru 100. Lets say its SUM.
2. Loop thru the input array. Substract each item from SUM.
You will have the missing number in SUM finally.
public static void main(String[] args) {
int input[] = { 2, 3, 4, 5, 6, 7, 8, 9, 28, 29, 30, 10, 11, 12, 13, 18,
44, 45, 74, 75, 76, 77, 21, 22, 78, 79, 80, 19, 20, 23, 24, 25,
26, 27, 31, 1, 32, 33, 34, 35, 36, 50, 51, 52, 53, 62, 63, 64,
70, 71, 85, 86, 87, 54, 37, 95, 96, 92, 93, 38, 99, 100, 83,
84, 17, 90, 91, 41, 39, 40, 97, 46, 66, 67, 68, 69, 47, 48, 49,
14, 15, 16, 72, 73, 98, 42, 43, 81, 82, 60, 61, 88, 89, 94, 55,
56, 57, 58, 59 };
int sum = (100*101)/2;
for (int i : input) {
sum -= i;
}
System.out.println("Missing number: " + sum);
}
sorry forgot the trippple action
def missing_val(unsorted_array):
input_set = set(unsorted_array)
input_min = min(unsorted_array)
input_max = max(unsorted_array)
test_set = set([x+1 for x in range(input_min,input_max)])
for x in test_set.difference(input_set):
return test_set.difference(input_set).pop()
the solution of the missing number is
public int missin (int num , int[] array)
{
int missingNum = ((Array.length(Array.length +1))/2) - (Sum of all elements in the array);
return missingNum;
}
My understanding of the problem is that there is an unsorted array containing 98 ints between 1 and 100, thus missing one value in that range.
- ZSGoldberg January 26, 2014The sum of numbers 1 through 100 is equal to (101*100)/2 = 5050
If we take the sum of the numbers in our array and subtract it from 5050 the result should be the one missing int.
Easy enough to code but I'm on mobile