public getMissingNum(A[]) {long arraySum = 0;long iSum = 0;for (int i = 0; i n + 1; i++) {iSum += i;arraySum += binaryToNum(A[i]);}missingNum = iSum - arraySum;return missingNum;}
public long binaryToNum( i ) {int powBy =0;long num = 0; long currentDigitValue = 0;while ( i 0) { int mod = i % 2;
Tru doing this:-
1.Take LSbit of all numbers and xor them.
2.Loop statment 1 for all bits.
3. U'll have the xor of all numbers present in A.
4. Start xor with numbers 1-N of the result above.
5. The number left after 5 is the number missing.
For more see this:-
hi asish,
thanks for ur reply..
But ur code takes O(n logn) to find the missing integer.
The binaryToNum() will returns num in O(log n ) complexity.
And there is a small mistake in ur code is it is not i =
i/10, it should be i = i/2
anil kumar wrote:
An array A[1..n] contains all the integers from 0 to n except one. It
would be easy to determine the missing integer in O(n) time by using an
auxilary array B[0..n] to record which numbers appear in A. In this
problem however we cannot access an entire integer in A with a
If the array may or may not contain the majority element, then after the
last step(ie once you get the get the array with one element) , just iterate
thru the original array once counting the number of occurences of this
element.
This along with karthik's logic works perfect. And it does not
