This problem may not be useful to many programmers professionally but it is (1) a way to get a job, (2) potentially part of some jobs, (3) an opportunity to learn more and think differently which is the point of these problems. We should be sensitive to those who have not drilled these concepts but we should also be curious about the problem-solving practice these problems provide. Be nice to each other people!

This is an interesting problem where brute-force is O(n) which is good for many problems but here you can do better. Optimizing the addition, xor, or test for equality is not useful because the worst-case time complexity will remain linear, though run time may occur in 0.8*n time. So, you must not bother evaluating numbers 0 through n. Instead, you need to find an intrinsic property about n to yield an answer. This suggest that there is a potential constant-time solution O(1) which would be optimal.

How do we do this? Enumerating scenarios can help get us thinking in binary. I suggest doing so for practice but during interview, don’t spend more time here than necessary to identify the pattern. Get creative about the relationships available (how many bits are there, how many times does XOR equal +?, is there a mathematical relationship between them? What other variables are available? # of 1’s? # of 0’s? How often will a match occur or not?). Don’t be thrown off by edge cases. Are there any inputs that stand out as not fitting a pattern?

Eventually, you may see that add’s and xor’s are equal under some condition and not equal under some other condition and that you can quantify that with just the information available.

Good luck!