R6300V2叫人失望# PDA - 掌中宝
b*e
1 楼
An array A[1...n] 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 opera-
tion. 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
Inspired by leetcode question, can we figure out 0^1^2^...^n first then do
an xor for each element in A? still O(n) time. although with a bigger
constant but much easier.
number which is
missing. In this problem, we cannot access an entire integer in A with a
single opera-
tion. 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
Inspired by leetcode question, can we figure out 0^1^2^...^n first then do
an xor for each element in A? still O(n) time. although with a bigger
constant but much easier.
