## 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.

Comment hidden because of low score. Click to expand.
-1

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.

Comment hidden because of low score. Click to expand.
5

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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;
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 * (a - 1) / 2);

System.out.println("missing number is = "+(realSum - arraySum));
}

}``````

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;
max_val = arr;
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);
int miss = missing_element(arr, size);
printf("MISSING VALUE: %-3d\n", miss);
return 0;
}``````

Comment hidden because of low score. Click to expand.
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

Comment hidden because of low score. Click to expand.
0

Perfect solution!

Comment hidden because of low score. Click to expand.
0

Moreover, this technique can be used to find even two missing elements from the original array. But this is already a different problem :)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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;

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

Comment hidden because of low score. Click to expand.
0

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

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,min=arr,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);
findMissingElement(arr,n);
}``````

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);
missing(A,n);
return 0;
}

void missing(int A[],int n)
{
int i,j;
int max,min;
max=min=A;
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);
}
}
}

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);
missing(A,n);
return 0;
}

void missing(int A[],int n)
{
int i,j;
int max,min;
max=min=A;
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);
}
}
}

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  #Max
y=a  #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}"``````

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+" and "+ip[ip.length-1]);
}

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+" and "+ip[ip.length-1]);
}``````

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+" and "+ip[ip.length-1]);
}//End of Main``````

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+" and "+ip[ip.length-1]);``

}

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

}

static void FindOneMissingNumber( int rangeStart, int rangeEnd)
{

int[] myList = Enumerable.Range(rangeStart, rangeEnd - rangeStart + 1).ToArray();

myList = 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));
}``````

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

}

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.

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;
max = a;
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= {11,12,13,14,16,17,18,19,10};
int size;
int res;
size = sizeof(arr)/sizeof(arr);
res=missingval(arr,size);
printf("\n%d",res);

getch ();

clrscr();
}``````

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;
max = a;
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;
}``````

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;

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;

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;
rangeMaxValue = arr;
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));
}}}

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {
Integer[] objArray = new Integer;
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);
}
}

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

You could use the divide and conquer method.

Comment hidden because of low score. Click to expand.
0

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

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``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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``````

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``````

Comment hidden because of low score. Click to expand.
0

The missing number is not known...

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

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

}``````

Comment hidden because of low score. Click to expand.
0

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

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

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

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

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.

### 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.