[第二轮] 3/25-3/31 CareerCup 5.7

An array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

/**
*  the number n is missing
*  count the bit one's number and bit zero's in the last bit of n, then judge second last bit of n, go on
*  why to judge the last bit to n?
*  As we know, 0,1,2,3,4...N: their last bit is 0 1 0 1 0 1;If there is a even missing num,
*  then the number of bit zero<=bit one; If a odd num is missed, then the bitzero>bit one.
*  By comparing the bit zero and bit one's count, we could know the last bit of the missing num.
*/
*/https://gist.github.com/Jnight/5261813 求测试，有加分

天道酬勤 发表于 2013-3-28 17:10
/**
*  divide and conquer
*  the number n is missing

题里面没有说数组是排好序的吧

默默的说个方法
全加起来，差哪个值不就看出来了？

menmen911 发表于 2013-3-29 10:03
默默的说个方法
全加起来，差哪个值不就看出来了？

In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A," which takes constant time. Write code to find the missing integer. 审题仔细啊同学 要求是O(n) time

也就是说，所有数字都是按10111100 这样排下来？ 中间有标点符号？

* method: 位操作无能。。。。。感觉对自己智力已经没勇气直视了。。。。和编程珠玑上面一道题比较类似
https://gist.github.com/xuyirio/3156330