CareerCup

say the nos are x to y with 1 missing no
temp1 = sum from 1 to y using the formula n(n+1)/2
temp2 = sum of 1 to x-1 using the formula n(n+1)/2
temp3 = sum of the given numbers
Missing no = temp1 - (temp3 + temp2)

<pre lang="" line="1" title="CodeMonkey4367" class="run-this">Java implementation of XOR algorithm, which is an O(n) solution, does not require sorted data input, and has no concern for overflow.

public static int findMissing(int[] arr) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

// find the inclusive range of the set of sequential numbers
for (int i : arr) {
if (i < min) {
min = i;
}
if (i > max) {
max = i;
}
}

int missing = 0;
for (int i = 0; i < arr.length; ++i) {
missing ^= arr[i];
}
for (int i = min; i <= max; ++i) {
missing ^= i;
}

return missing;
}
</pre>

given set of sequential numerbs means its sorted

so assume u ll decrement all array values by (a[0]+1) then the data becomes 1,2,3,4,...,n
find the mising number here and add (a[0]-1) to it

The numbers in the array are sorted.
Get the median, compare (median-first) and
((index of median)-(index of first)),
(last-median) and ((index of last)-(index of median)).

Then you can determine which half this missing number is in.

Then take the sub array, get median, compare, half ...
Running time is O(lgn)

Great soln ..

say the set {1,2,...n}
define an array, arr[n], iter the set and put 1 in the corresponding element.
Missing numbers will have 0

Add them all up, get the sum of all expected numbers between x and y, the difference is the number missing.

modified binary search algorithm

<pre lang="" line="1" title="CodeMonkey64489" class="run-this">Java implementation of XOR algorithm, which is an O(n) solution, does not require sorted data, and has no concern on overflow.

public static int findMissing(int[] arr) {

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int missing = 0;

/* xor all numbers in the set and find the inclusive
range of the set of sequential numbers */
for (int i : arr) {
missing ^= i;
if (i < min) min = i;
if (i > max) max = i;
}

// XOR all numbers within the range inclusively
for (int i = min; i <= max; ++i) {
missing ^= i;
}

return missing;
}
</pre>

Some of the solutions provided above expects difference of 1 within nos. in a sequence. Following solution can take any sequence provided the difference between nos. is consistent (in Arithmetic progression); except with the missing value.
//test cases:
int []arr = {-20,-14,-2,4}; //gives -8 , diff of 6
int []arr = {10,30,40}; //gives 20, diff of 10
int []arr = {2,6,8,10}; //gives 4, diff of 4

public static int myFindMissing(int []arr)
    {
        int diff=0;
        int prevDiff=Integer.MIN_VALUE;
        int i=1;
        for(;i<arr.length;i++)
        {
            diff = arr[i]-arr[i-1];
            if(diff!=prevDiff)
            {
                if(i==2)
                {
                    i=1;
                    prevDiff = diff;
                    break;
                }
                if(prevDiff==Integer.MIN_VALUE)
                    prevDiff=diff;
                else
                    break;
            }
        }       
        return(arr[i-1]+prevDiff);
    }