CareerCup

(sum of 1 to 1000) - (sum of 999 distinct integers) = missing number

But it says - can't allocate an additional array.

boolean flag = false;
for (int i = 0; i < a.length; i++) {
if (i + 1 == a[i]) {
continue;
} else {
flag = true;
System.out.println(i + 1);
break;
}
}
if (!flag) {

System.out.println("1000");
}

array should be sorted, if not then this code will not run !

Cumulative XOR of numbers in the array and the their index will give the missing number in the end. Time Complexity O(n). Space complexity O(1)
Note: The sum method suffers with an overflow problem in the general case.

the array need not be sorted and the problem can be solved in O(n)
we know the formula, for sum of n numbers from 1 to n is n*(n+1)/2
code:
int missing_number(int len, int a[])
{
sum=len*(len+1)/2;
for(int i=0; i<len;i++)
{
sum=sum-a[i];
}
return (sum);
}

Assuming that number are not sorted and numbers are between 1 and 999.
now subtract the first number with 1000. do this with all the element of the array and insert the reminder in a hash table.
Before subtraction, find the element in the hash table and delete it if found. At last you will left with the missing number.
there might be some more correction.. but this is the heart of my algo.

Sum of n numbers = n(n+1)/2 : 1000(1001)/2 = 500500

Subtract the total sum of the given number from 500500.

suppose array is {3,5,1,4} and range is 1-5 missing numeber is 2

so XOR of array is 3^5^1^4
and XOR OF RANGE is 1^2^3^4^5
because XOR of two number is 0 ....

(1^2^3^4^5)^(3^5^1^4)=2 result

The very efficient way to find the missing integer from the array we will first xor all the numbers from 1 to n, then we will xor all the array element numbers and then at the end we will xor the both of them to get the missing number in the array.

Implementation:

int findmissing(int arr[], int n){
	int xor_number = 1;
	int xor_array = arr[0];
	for(int i = 2; i <= n + 1; i++)
		xor_number = xor_number ^ i;
	for(int i = 1; i < n; i++)
		xor_array = xor_array ^ arr[i];
	return xor_array ^ xor_number;
}