Interview Question for Financial Software Developer at Bloomberg L.P.:

100

1. calculate the sum of elements in array say SUM
2. sum of numbers 1 to 100 is(n* (n+1))/2 = 5050 when n==100
3. missing element is (5050-SUM)

100

The parameters of the question do not allow you to determine what element is missing. Either more information should be supplied, or all answers are equally correct.

How could an array size of 99 elements contain 1 - 100? Should either be integers 1-99 or 2-100 , in either case there is no missing element. All indices are accounted for.

Sum them and then subtract them from 5050.

In general, if an array of size n - 1 elements has unique elements from 1 to n, then the missing element can be found by subtracting the sum of the elements in the array from sum(1 ... n) = n * (n + 1) / 2.

Alternately, one could use a boolean array of length n with all values set to false and then for each value, set array[val - 1] to true. To find the missing value, scan through the array and find the index which is set to false. Return index + 1. This requires O(n) memory and two passes over an O(n) array (instead of constant memory and one pass), but has the advantage of actually allowing you to verify whether or not the input was well formed.

Admittedly, this question is poorly posed; however, the answer they are looking for refers to the syntax/nomenclature of some (not all) programming languages to index arrays starting at “0.” As such the 1-100 stored values would be in entries 0-99 of the array.

Read the question. Here are the steps to solve it:
1) find the sum of integers 1 to 100
2) subtract the sum of the 99 members of your set
3) the result is your missing element!
Very satisfying!

Sort array.

While loop with an index variable with condition of next element being 1 greater than previous element.

When loop breaks, return the value of the index.

Doing the expected sum and subtracting the actual gives the run time of O(2n), however a bucket sort will almost always do it in less time (somewhere between O(n) and O(2n)):

1. create a 101-int (or boolean) array (to have a 100-index)
2. traverse original and for each int, assign value in bucket array to 1 or true.
3.After first traversal, traverse created array starting at one, and when value is false, print it.

100

100 coz in array it initial value starts frm 0 to 100. or else 4 further clarification u can study array chapter in c or c++

100

The question:
"An array of 99 elements contains integers from 1 to 100 with one missing element. Find the missing element."
The information states that the integer count is 1 to 100. I take this to be inclusive of all elements in the array so that the missing inters would be subjective to their arrangement or random. In other words, I do not have enough information to say which one.

1

I need more information.
1. Are the integers unique in this array?
2. Do I have enough information to find the sum of the integers in the array (or some aggregation)?
If sum is available, then, the answer is 5050-sum{integers}.

Bucket Sort works and summation works. I think both are good, practical and clever solutions. I think sorting the array then searching may be unnecessary computation.

Another interesting method which may be faster. SIMD computers may do this particularly quickly:

Do a bitwise operation on all the elements:

Result = Array[0] xor Array[1] xor ... Array[98] xor 1 xor 2 xor ... xor 100

Result = Missing number.

Explanation:

When you xor 2 identical numbers your result = 0. For example, 5 xor 5 -> 101 xor 101 = 000. (5 in decimal is 101 in binary). Knowing that "xoring" 2 identical numbers results in zero is useful.

Now we apply this useful info to the problem. Array is Identical to a list of 1,2,3,...,100 except for one number. In other words 1,2,3,...,100 duplicates all of array's elements and adds one extra element that is missing in Array. Therefore, we now have 2 instances of each element in the Array in addition to one extra element in 1,2,3,...,100. We can see when you xor two duplicate numbers you get zero. Because we have pairs for all numbers in Array and one extra number we are essentially "xoring" the missing number with zero. When we xor the missing number with zero we get the missing number. (For example, 6 xor 0 -> 110 xor 000 = 110)