Amazon Interview Question for Quality Assurance Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
10
of 16 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 votes

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.

- Kedar Joshi July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 votes

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.

- oOZz July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Summing up the numbers might very easily overflow, in which case you will surely lose the end result.

- ashot madatyan July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashot madatyan July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Chih.Chiu.19 July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- iammrigank July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Kazi August 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- sourav.palmal August 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
9
of 9 vote

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

- ashot madatyan July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kedar Joshi July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Perfect solution!

- Murali Mohan July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ashot madatyan
Nice solution! Just curious: what's your approach to find two missing numbers?... Thanks.

- Chih.Chiu.19 July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Chih.Chiu.19 July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ashot madatyan July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I second @Chih.Chiu.19, this is a good solution and it's well written. +1 my friend.

- oOZz July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Seth July 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this assumes the numbers are sorted... good solution anyways

- koshinski December 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vgeek July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}
}
}

- Rahul singh July 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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);
}
}
}

- Rahul singh July 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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}"

- Nitin July 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
}

- Anonymous July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
	}

- Praveen D July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Praveen D July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);

}

- Praveen D July 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Anonymous August 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Aparna September 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# 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();
}

- abhi.20dec September 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sakthivel Sethu,Software Engineer ,Bangalore October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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;

- NIPUN GUPTA January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/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;

- nipungupta.ng January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nilanchal June 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Suresh May 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Suresh May 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- GK May 03, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zr.roman May 10, 2023 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

You could use the divide and conquer method.

- ash July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Mohammed.Alghzawi July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Bimlesh July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not to check if the number is in the list or not, we have to find out wat is the missing number?

- radibioinfo July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction:

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:
         pass
     else:
          print  Y,"tnumber not in list"
          break
     Y+=1

- bimleshsharma July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Then it is more simple.

if miss_num in list:
     pass
else:
    print "missing number is", miss_num

- bimleshsharma July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The missing number is not known...

- radibioinfo July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Assuming that the 100 numbers are consecutive, you can sort the array in increasing order and then check for adjacent locations to find the missing number

- Kedar Joshi July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

- radibioinfo July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kedar Joshi July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 5 vote

Find the sum of all the element in the array, say it is arraySum
Now, sum of n number is n(n+1)/2, say sum
So missing number is sum-arraySum

- Fargushan July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Kedar Joshi July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

First correction array would conatin 99 elements as one is missing..assuming so

here is the python code

#!/usr/bin/python
a=[int(i) for i in raw_input().split()]
min_=min(a) #assuming the numbers start with some other number than 1
sum_=sum(a)
print sum_- 100*(min_*2+99)

- sarath s pillai July 26, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More