Amazon Interview Question
Quality Assurance EngineersCountry: United States
Interview Type: Phone Interview
This method will work only when the numbers are beginning from 1.
what if my array has numbers from 1111 to 1211 ? I believe your method will not work.
This is still the right approach even if the numbers are not starting from 1. You can simply normalize the numbers, e.g., from (1111-1111) to (1211-1111) and then return (result+1111).
+1 from me.
Summing up the numbers might very easily overflow, in which case you will surely lose the end result.
@ashot madatyan I'd agree with you, if the problem didn't say that there are only 100 numbers. Again, if you normalize the upper and lower bounds, the sum will always be 5050, so you can even define this as a constant.
@oOZz This should work only for the given range of numbers [1 ... 100], but what I suggested will work for any range, even with the numbers that would overflow should they be summed up. Consider input values as follows [ INT_MAX - 2, INT_MAX - 5, INT_MAX - 20, ...] Will your suggested algo work for this series of numbers ? I believe the answer is "No".
@oOZz & ashot madatyan
Hey, oOZz is right about the bound: because even in your solution below (it is cool btw, and I already bookmarked it :)) you need to know the lower bound of the array, right? Then instead of summing the entries of the array directly you can just sum (entry-lower bound) which will fits into the INT range (well, unless N is extremely large...)
Undoubtedly, @Ashok's solution is very elegant. But i believe that ^this^ solution is more
general because the numbers just have to be "evenly" spaced for this to work.
x, x+a, x+2a, ... , x + (n-1)*a
for (n-1) elements (missing one)
...can also be found.
Yes, for very large inputs, this will break down. But that ignored, this is more general.
This will work if you calculate 1 to 1211 and 1 to 1110 using the summation formula. Then take the difference, which will give you the sum of 1111 to 1211.
i think this is the most simplest and easiest solution.
running code :
package amazon.arrays;
public class OneMissingNumber {
/**
* @param args
*/
public static void main(String[] args) {
int[] arr = new int[99];
for (int x = 0; x < arr.length; x++)
if (x != 45){
//skip 1 elemnt 6894+45 = 6939 is skipped
arr[x] = x + 6894;
}
getMissing(arr);
}
static void getMissing(int a[]) {
int arraySum = 0;
for (int x = 0; x < 99; x++) {
arraySum += a[x];
}
int realSum = (a[a.length - 1] * (a[a.length - 1] + 1) / 2);
realSum -= (a[0] * (a[0] - 1) / 2);
System.out.println("missing number is = "+(realSum - arraySum));
}
}
There is a very elegant solution using bitwise operations with integers.
The following solution has O(n) time and O(1) space:
INPUT: arr[N] = min_val, i.e. min_val + 1, min_val + 2, .... max_val
MISSING: min_val < missing_val < min_val + N
ASSUMPTION: There are no duplicates in the input array
Solution:
0. Find the minimum and maximum values in the array: min_val, max_val
1. Compute the XOR'ed value of all elements from min_val to max_val inclusive: <xc>
2. Compute the XOR'ed value of all the input array elements: <xarr>
3. XOR the two integers - this will produce the missing element's value
The s/c and the test harness are below:
#include <stdio.h>
int missing_element(int arr[], int size)
{
int min_val, max_val;
int xarr = 0, xacc = 0;
// Find the minimum and maximum values in the array
min_val = arr[0];
max_val = arr[0];
for (int i = 1; i < size; ++i){
if (arr[i] > max_val)
max_val = arr[i];
if (arr[i] < min_val)
min_val = arr[i];
}
// Find the XOR'ed value of all numbers from min_val to max_val inclusive
for (int i = min_val; i <= max_val; ++i) {
xacc ^= i;
}
for (int i = 0; i < size; ++i){
xarr ^= arr[i];
}
return (xacc ^ xarr);
}
int main()
{
// values are 5 - 14, missing is 11
int arr[] = {8, 13, 5, 10, 6, 7, 9, 12, 14};
int size = sizeof(arr) / sizeof(arr[0]);
int miss = missing_element(arr, size);
printf("MISSING VALUE: %-3d\n", miss);
return 0;
}
The solution mentioned by ashot madatyan works perfect !
Since it works in O(n) time then its the best solution. Mine works in O(n log n) so we have two solutions here
Moreover, this technique can be used to find even two missing elements from the original array. But this is already a different problem :)
@ashot madatyan
Nice solution! Just curious: what's your approach to find two missing numbers?... Thanks.
@ashot madatyan
I forgot to say that I really like your code a lot, not only because it is well formatted, but also it is well commented, tested, and it has a short but precise explanation block for the algorithm that comes with it --- thanks a lot!
@Chiu.Chiu You have two arrays, each containing non-repeating integers. The second array is the same as the first except the second array is missing two integers from the first array. How would you find in O(N) time and O(1) space those two integers that are missing in the second array?
Pretty simple C# solution:
public static int MissingNumber(int[] theArray)
{
int theNum = theArray[0];
for (int i = 0; i < theArray.Length; i++)
{
if (theArray[i] != theNum)
{
Console.WriteLine("The missing number is {0}", theNum);
break;
}
else
{
theNum++;
}
}
return theNum;
}
Here another method is used to find any number of missing numbers within a given range:
a. Get the min and max of the array.
b. Make the count array of size max.
c. Store INT_MIN values in the count array till min that is from 0 to min-1 as this is not the range to search for.
d. Make the rest of the elements from min to max to 0
e. At last increment the count for every value.
f. For those elements for which the count is 0 they are missing. Here is the code:
#include <stdio.h>
#include <conio.h>
#include <limits.h>
int findMissingElement(int arr[],int n)
{
int max=arr[0],min=arr[0],i;
for(i=0;i<n;i++)
{
if(max<arr[i])
max=arr[i];
if(min>arr[i])
min=arr[i];
}
int count[max];
for(i=0;i<min;i++)
count[i]=INT_MIN;
for(i=min;i<=max;i++)
count[i]=0;
for(i=0;i<n;i++)
{
count[arr[i]]++;
}
for(i=min;i<=max;i++)
{
if(count[i]==0)
{
printf(" %d ",i);
}
}
}
int main()
{
int arr[]={12,14,15,16,13,20};
int n=sizeof(arr)/sizeof(arr[0]);
findMissingElement(arr,n);
}
#include<stdio.h>
void missing(int [],int);
int main()
{
int A[]={4,3,5,2,8,9,6,10,13,11,12};
int n=sizeof(A)/sizeof(A[0]);
missing(A,n);
return 0;
}
void missing(int A[],int n)
{
int i,j;
int max,min;
max=min=A[0];
for(i=0;i<n;i++)
{
if(max<A[i])
max=A[i];
if(min>A[i])
min=A[i];
}
int c[max];
for(i=0;i<max;i++)
{
c[i]=0;
}
for(i=0;i<max;i++)
{
c[A[i]]=c[A[i]]+1;
}
for(j=min;j<max;j++)
{
if(c[j]==0)
{
printf("the missing no is= ");
printf("%d ",j);
}
}
}
#include<stdio.h>
void missing(int [],int);
int main()
{
int A[]={4,3,5,2,8,9,6,10,13,11,12};
int n=sizeof(A)/sizeof(A[0]);
missing(A,n);
return 0;
}
void missing(int A[],int n)
{
int i,j;
int max,min;
max=min=A[0];
for(i=0;i<n;i++)
{
if(max<A[i])
max=A[i];
if(min>A[i])
min=A[i];
}
int c[max];
for(i=0;i<max;i++)
{
c[i]=0;
}
for(i=0;i<max;i++)
{
c[A[i]]=c[A[i]]+1;
}
for(j=min;j<max;j++)
{
if(c[j]==0)
{
printf("the missing no is= ");
printf("%d ",j);
}
}
}
Ruby Code
p=0
a=Array.new
b=Array.new
a=[3,2,4,7,8,1]
l=a.length
puts l
x=a[0] #Max
y=a[0] #Min
#Min Max calualtion
for i in 1...l
if( x < a[i])
x=a[i]
else
if (y > a[i])
y=a[i]
end
end
end
c=0
flag=0
#Finding Missing value
for p in y..x
flag=0
for i in 0..l
if(p==a[i])
flag=1
break
else
flag=0
end
end
if flag==0
b[c]=p
c=c+1
end
end
puts "Missing values = #{b}"
public static void main(String[] args)
{
int[] ip = {1,2,3,4,5,6,7,8,9,10}; //5 is Missing
Arrays.sort(ip);
for(int i=0; i<ip.length-1; i++)
{
if(i==0 && ip[i]<ip[i+1]){
continue;
}else if(ip[i]>ip[i-1] && ip[i]<ip[i+1] && ( (ip[i-1]+1)==ip[i]) && ( (ip[i+1]-1)==ip[i]) ){
continue;
}else{
System.out.println("Missing Number is : "+(ip[i]+1));
break;
}
}
System.out.println("All the Numbers are present between "+ip[0]+" and "+ip[ip.length-1]);
}
public static void main(String[] args)
{
int[] ip = {1,2,3,4,5,6,7,8,9,10}; //5 is Missing
Arrays.sort(ip);
for(int i=0; i<ip.length-1; i++)
{
if(i==0 && ip[i]<ip[i+1]){
continue;
}else if(ip[i]>ip[i-1] && ip[i]<ip[i+1] && ( (ip[i-1]+1)==ip[i]) && ( (ip[i+1]-1)==ip[i]) ){
continue;
}else{
System.out.println("Missing Number is : "+(ip[i]+1));
break;
}
}
System.out.println("All the Numbers are present between "+ip[0]+" and "+ip[ip.length-1]);
}
public static void main(String[] args)
{
int[] ip = {1,2,3,4,5,6,7,8,9,10}; //5 is Missing
Arrays.sort(ip);
for(int i=0; i<ip.length-1; i++)
{
if(i==0 && ip[i]<ip[i+1]){
continue;
}else if(ip[i]>ip[i-1] && ip[i]<ip[i+1] && ( (ip[i-1]+1)==ip[i]) && ( (ip[i+1]-1)==ip[i]) ){
continue;
}else{
System.out.println("Missing Number is : "+(ip[i]+1));
break;
}
}
System.out.println("All the Numbers are present between "+ip[0]+" and "+ip[ip.length-1]);
}//End of Main
public static void main(String[] args)
{
int[] ip = {1,2,3,4,6,7,8,9,10}; //5 is Missing
Arrays.sort(ip);
for(int i=0; i<ip.length-1; i++)
{
if(i==0 && ip[i]<ip[i+1]){
continue;
}else if(ip[i]>ip[i-1] && ip[i]<ip[i+1] && ( (ip[i-1]+1)==ip[i]) && ( (ip[i+1]-1)==ip[i]) ){
continue;
}else{
System.out.println("Missing Number is : "+(ip[i]+1));
break;
}
}
System.out.println("All the Numbers are present between "+ip[0]+" and "+ip[ip.length-1]);
}
Here is c# solution in o(n) complexity:
//Given you an array of 100 Elements with one number missing, how will you find the missing number?
//Example 1: Array 1 to 100 with 100 missing.
//Example 2: Array 1111 to 1211 with 1210 missing.
class FindMissingNumber
{
static void Main( string[] args)
{
FindOneMissingNumber(1, 100);
Console.ReadKey();
}
static void FindOneMissingNumber( int rangeStart, int rangeEnd)
{
int[] myList = Enumerable.Range(rangeStart, rangeEnd - rangeStart + 1).ToArray();
myList[99] = 0;
int n = myList.Count();
int origSum = (n * (n + 1)) / 2;
int calSum = 0;
for ( int i = 0; i < myList.Count(); i++)
{
if(myList[i] != 0)
calSum += myList[i] - rangeStart + 1;
}
Console.WriteLine( "Missing Number: {0}", (origSum - calSum + rangeStart - 1));
}
public void missingNumber() {
int series[] = { 1, 2, 4, 6, 3, 5, 7, 8, 9, 10, 11, 12, 13, 14,15, 18, 16,17,20};
Arrays.sort(series);
int length = series.length;
int first = series[0];
int last = series[length - 1];
int totalNumbers = length + 1;
int actualSum = 0;
for (int i = 0; i < length; i++) {
actualSum = actualSum + series[i];
}
int sum = totalNumbers * (first + last) / 2;
System.out.println("missing number: " + (sum - actualSum));
}
For finding two missing numbers, using @ashot madatyan's solution:
Original procedure to find xor remains same.
However, in case of two missing numbers, this value is the difference of the two numbers. E.g if range is { 1,3,4,5,6,8,9,10} the missing numbers are 7 and 2.
The final xor value will be 5.
This is the difference 7-2 = 5.
While running the xor loops , compute OR of all elements.
Subtract the sum of all array elements from elements in range. This gives us the sum of the missing numbers. In our example, this will be 9.
Now, we have the sum and difference of the missing numbers.
Simply OR these values, and divide by 2 to get 1 number. ( 9 | 5) /2 = 7
XOR the result with difference of numbers to get the second number. ( 5 ^ 7) = 2
This is ofc, assuming summing the array and range does not overflow int value.
This approach will fail in that case.
# include <stdio.h>
# include <conio.h>
int missingval(int a[], int s)
{
int i, min, max, sum,suma;
min = a[0];
max = a[0];
for(i=0;i<s-1;i++)
{
if(a[i] < min)
min = a[i];
if(a[i] > max)
max = a[i];
}
printf("min = %d, max=%d\n",min,max);
sum=0;
for(i = 0 ; i < s ; i++)
{ sum += a[i];
// printf("sum %d %d %d\n",i,sum,a[i]);
}
suma=min;
for(i=min+1 ; i<=max ; i++ )
{
suma +=i;
printf("sum %d %d\n",i,suma);
}
printf("%d", suma-sum);
return(suma-sum);
}
void main ()
{
int arr[10]= {11,12,13,14,16,17,18,19,10};
int size;
int res;
size = sizeof(arr)/sizeof(arr[0]);
res=missingval(arr,size);
printf("\n%d",res);
getch ();
clrscr();
}
#include<stdio.h>
int main()
{
int a[] = {12,11,13,14,16,17};
int i,n,min,sum =0, max,MAX;
int formula;
min = a[0];
max = a[0];
MAX = (sizeof(a)/sizeof(int));
for(i=0;i<MAX;i++)
{
if(max<a[i])
max=a[i];
if(min>a[i])
min=a[i];
}
printf("min = %d, max=%d\n",min,max);
n = (sizeof(a)/sizeof(int))+1;
formula = (n*((2*min)+((n-1)*1)))/2;
for(i=0;i<MAX;i++)
sum+=a[i];
printf("Missing number is : %d \n ",(formula-sum));
return 0;
}
#!/usr/bin/perl
my @arr = (1,29,30,31,32,33,34,35,36,37,2,13,14,15,16,17,18,19,20,21,22,3,4,5,6,7,8,9,10,11,12,23,24,25,26,27,28,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,83,84,85,86,87,88,89,90,91,56,57,58,59,60,61,62,63,64,65,66,67,80,81,82,92,93,94,95,96,97,98,99,100,68,69,70,71,72,73,74,75,76,77,78,79);
$max = -1;
$min = 999;
$val1 = 0;
$val = 0;
foreach(@arr){
if($_ > $max){
$max = $_;
}
if($_ < $min){
$min = $_;
}
$val = $val ^ $_;
}
my $length = $#arr + 1;
for($i = $min;$i <= $max;$i++){
$val1 = $val1 ^ $i;
}
$result = $val1 ^ $val;
print "\n RESULT = " , $result;
#!/usr/bin/perl
my @arr = (1,29,30,31,32,33,34,35,36,37,2,13,14,15,16,17,18,19,20,21,22,3,4,5,6,7,8,9,10,11,12,23,24,25,26,27,28,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,83,84,85,86,87,88,89,90,91,56,57,58,59,60,61,62,63,64,65,66,67,80,81,82,92,93,94,95,96,97,98,99,100,68,69,70,71,72,73,74,75,76,77,78,79);
$max = -1;
$min = 999;
$val1 = 0;
$val = 0;
foreach(@arr){
if($_ > $max){
$max = $_;
}
if($_ < $min){
$min = $_;
}
$val = $val ^ $_;
}
my $length = $#arr + 1;
for($i = $min;$i <= $max;$i++){
$val1 = $val1 ^ $i;
}
$result = $val1 ^ $val;
print "\n RESULT = " , $result;
Calling Code:
// It works for any range. You can pass a range or simply pass an array. accordingly pass the boolean value for rangePassed.
int arr[] = { 11, 12,13,18,20 };
findAnyMissingGeneric(10,25,arr,true); // with range
//findAnyMissingGeneric(0,0,arr,false); // without range
Called Code:
private static void findAnyMissingGeneric(int rangeMinValue, int rangeMaxValue, int[] arr, boolean rangePassed) {
int range_length = 0;
if(!rangePassed){// find the min & max of the range
rangeMinValue = arr[0];
rangeMaxValue = arr[0];
for (int i = 1; i < arr.length; ++i) {
if (arr[i] > rangeMaxValue)
rangeMaxValue = arr[i];
if (arr[i] < rangeMinValue)
rangeMinValue = arr[i];
}
range_length = arr.length; }else{
range_length = (rangeMaxValue-rangeMinValue)+1; }
System.out.println("range_length: "+range_length+" :rangeMaxValue: " + rangeMaxValue + " :rangeMinValue: " + rangeMinValue);
int b[] = new int[rangeMaxValue];
for (int i = 0; i < arr.length; i++) {
b[(arr[i] - 1)] = arr[i]; }
for (int i = rangeMinValue-1; i < rangeMaxValue; i++) {
if (b[i] == 0) {
System.out.println("missing number is" + (i + 1));
}}}
Guys,
Why don't we use the following option.
public static void main(String[] args) {
Integer[] objArray = new Integer[100];
for (int i=0;i<100;i++)
{
objArray[i]=i;
}
Set<Integer> objList1 = new HashSet(Arrays.asList(objArray));
objList1.remove(55);
System.out.println("1st List size"+objList1.size());
Set<Integer> objList2 = new HashSet(Arrays.asList(objArray));
objList2.removeAll(objList1);
System.out.println("Length is "+objList2.size());
for (Integer i : objList2)
{
System.out.println("Missing element is "+i);
}
}
public static void main(String[] args) {
Integer[] objArray = new Integer[100];
for (int i=0;i<100;i++)
{
objArray[i]=i;
}
Set<Integer> objList1 = new HashSet(Arrays.asList(objArray));
objList1.remove(55);
System.out.println("1st List size"+objList1.size());
Set<Integer> objList2 = new HashSet(Arrays.asList(objArray));
objList2.removeAll(objList1);
System.out.println("Length is "+objList2.size());
for (Integer i : objList2)
{
System.out.println("Missing element is "+i);
}
}
public static Integer missingNumber(int[] a, int startNum) {
Arrays.sort(a);
int tempNum = startNum;
for(int i=0; i<a.length; i++) {
if(a[i]!=tempNum) {
break;
} else {
tempNum++;
}
}
return tempNum;
}
public static void main(String[] args) {
int[] a = {1,2,3,5,6,7,8,9,10};
System.out.println("Missing Number is: " + missingNumber(a, 1));
}
Working solution, space O(n), about time I am not sure, looks like O(n) or at max O(n*logn)
namespace ConsoleApp {
internal class Program {
private static Random rnd = new Random();
static void Main(string[] args) {
var N = 100;
while (N-- > 0) {
var min_number = 1; //rnd.Next(0, 50);
var max_number = 20;//rnd.Next(51, 61);
var missing_number = rnd.Next(min_number, max_number + 1);
var arr = new int[max_number-min_number];
var needIncrementBy1 = false;
for (int i = 0; i <= max_number - min_number-1; i++) {
if (i + min_number == missing_number) {
arr[i] = i + 1 + min_number;
needIncrementBy1 = true;
continue;
}
if (!needIncrementBy1) {
arr[i] = i + min_number;
} else {
arr[i] = i + 1 + min_number;
}
}
var res = GetMissingNumber(arr, min_number, max_number, out int?[] new_arr);
if (res != missing_number)
{
throw new Exception("Error!!!");
}
}
}
public static int GetMissingNumber(int[] A, int min_number, int max_number, out int?[] arr) {
arr = new int?[A.Length + 1];
for (int i = 0; i < arr.Length; i++) {
if ( i == arr.Length - 1 ) {
arr[i] = null;
break;
}
arr[i] = A[i];
}
for (int i = 0; i <= max_number - min_number; i++) {
Swap(arr, rnd.Next(0, max_number - min_number+1), rnd.Next(0, max_number-min_number+1));
}
var counter = 0;
while (true) {
counter++;
var needBreak = true;
for (int i = 0; i <= max_number - min_number; i++) {
if (arr[i] != null && i != arr[i]!.Value - min_number) {
Swap(arr, i, arr[i]!.Value - min_number );
}
}
for (int i = 0; i <= max_number - min_number; i++) {
if (arr[i] == null) {
continue;
}
if (arr[i] - min_number != i) {
needBreak = false;
break;
}
}
if (needBreak) {
break;
}
}
var res = -1;
for (int i = 0; i <= max_number - min_number; i++) {
if (arr[i] == null) {
Console.WriteLine(string.Empty);
Console.WriteLine($"min_number: {min_number}");
Console.WriteLine($"max_number: {max_number}");
Console.WriteLine($"{i+min_number} is missing");
Console.WriteLine($"Counter: {counter}");
res = i + min_number;
break;
}
}
return res;
}
private static void Swap(int?[] arr, int i, int j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
public class findMissingnumbers {
/**
* @param args
*/
public static void main(String[] args) {
// 0-100
int[] a = {1, 4, 3, 6, 7, 9, 8, 11, 10, 12, 15, 18, 14};
printMissingNumbers(a, 100);
}
public static void printMissingNumbers(final int[] a, final int upperLimit) {
int b[] = new int[upperLimit];
for (int i = 0; i < a.length; i++ ) {
b[a[i]] = 1;
}
for (int k = 0; k < upperLimit; k++ ) {
if (b[k] == 0)
System.out.println(k);
}
}
}
def find_missing():
l=list(x for x in range(1,101))
l.remove(55)
print l
Y=1
for x in l:
if x==Y:
continue
else:
print Y,"tnumber not in list"
break
Y+=1
Not to check if the number is in the list or not, we have to find out wat is the missing number?
Then it is more simple.
if miss_num in list:
pass
else:
print "missing number is", miss_num
Something like this... the first for is just to setup the array with the missing number.
public class MissingNumber {
public static void main(String[] args) {
List <Integer> l = new ArrayList<Integer>();
int[] ar= new int[100];
//Setup with missing number ex: 87
for(int i=0;i<100;i++)
{
if(i!=87){
ar[i]=i;
}
}
//To find out missing number
for(int i=0; i<ar.length-1;i++){
if(ar[i]+1==ar[i+1]){
continue;
}
else{
int missing=ar[i]+1;
System.out.println("Missing Number "+missing);
break;
}
}
}
}
Yes, something like that. My approach is slightly different.
If we do not know the missing number then I think following solution should work. Please try it out.
Sort the initial array. (Merge sort will be better since its faster)
void findMissing(int arr[])
{
// sorted array - arr[]
for(int i=0; i< arr.length; i++)
{
if(arr[i] < arr[i+1]
{
// do nothing since this is expected
}
else
{
// since the array is sorted, this is the only condition when it should detect a
// number as missing
Print Missing Number as arr[i] + 1;
}
}
}
Sorry, correction to my previous answer -
Sort the initial array. (Merge sort will be better since its faster)
void findMissing(int arr[])
{
// sorted array - arr[]
for(int i=0; i< arr.length; i++)
{
if(arr[i] < arr[i+1] && arr[i+1] - arr[i] == 1)
{
// do nothing since this is expected
}
else
{
// since the array is sorted, this is the only condition when it should detect a
// number as missing
Print Missing Number as arr[i] + 1;
}
}
}
Really? :)... Just do sum of all the numbers from 1 to 100 : (n * (n+1))/2 and find sum of all the elements from actual array. Just take the difference and you will get missing number.
- Anonymous July 25, 2013