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;
i = i / 10;
if (mod == 1)
{
currentDigitValue = (long)Math.pow(2,powBy);
num = num + currentDigitValue;
}
powBy ++;
}
return num;
}
Regards,
Ashish
On 6/21/06, anil kumar <
[EMAIL PROTECTED]> 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 single
operation. The elements of A are represented in binary, the only
operation we can use to access them is " Fetch the jth bit of A[i] " ,
which takes constant time. Find the missing integer in O(n) time using
only that operation.
Thanks,
Regards
Anil.
--
///\\
(@ @)
+----oOO----(_)-----------------------+
| ~~~ |
| Phone: +91(40)5511 1552 |
| ~~~ |
| Disclaimer: |
| The Statement and options |
| expressed here are my own |
| do not necessarily represent |
| those of Oracle Corp. |
+-----------------oOO-------------------+
|__|__|
|| ||
ooO Ooo
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
