We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
here is a C++ solution that uses only 32 and 64 bit integers, and passes all test cases in O(lg a + lg b) time and space (took me about 4 hours of debugging, so the code is a bit messy, but I finally got it to work, and it runs very fast). No recursion or dynamic programming is used.
The basic idea is that only the first approximately lg a terms in the sum require any actual XOR to be done; for the rest of the terms, a and b are "decoupled" and XOR is equivalent to addition, so that part of the sum can be computed in O(1) time.
The XOR in the first lg a terms can be done by "sliding" b through a, and for each bit in a (as well as the zeros padding a from above), we can count the number of zeros and ones that will "hit" that bit in O(1) time per bit, provided that we precompute the number of ones and zeros in b, which takes O(lg b) time.
Xor and Sum
You are viewing a single comment's thread. Return to all comments →
here is a C++ solution that uses only 32 and 64 bit integers, and passes all test cases in O(lg a + lg b) time and space (took me about 4 hours of debugging, so the code is a bit messy, but I finally got it to work, and it runs very fast). No recursion or dynamic programming is used.
The basic idea is that only the first approximately lg a terms in the sum require any actual XOR to be done; for the rest of the terms, a and b are "decoupled" and XOR is equivalent to addition, so that part of the sum can be computed in O(1) time.
The XOR in the first lg a terms can be done by "sliding" b through a, and for each bit in a (as well as the zeros padding a from above), we can count the number of zeros and ones that will "hit" that bit in O(1) time per bit, provided that we precompute the number of ones and zeros in b, which takes O(lg b) time.