Bit Manipulation
Retrieval: when do bits help?
Two problems rebuilt cold, plus the signals that a problem wants bitwise thinking.
Key idea
Three tells
Everything appears an even number of times except one thing. That is self-cancellation, and it is the strongest signal in this unit.
The problem demands constant extra space and involves counting or pairing. A hash map is the obvious solution and the space requirement is ruling it out.
The problem mentions a fixed width, a 32-bit range, or forbids the arithmetic operators. Then the width handling is the problem rather than an implementation detail.
Tip
One more use worth knowing
A set of up to about twenty elements can be represented as a single integer, one bit per element. Then subsets are integers, union is or, intersection is and, and iterating every subset is a loop from zero upward.
That is the bitmask technique, and it turns some subset problems from U10 into short loops. No problem in this course needs it, and it appears often enough in harder interviews to be worth knowing the name of.
Does this want bits?
Every value in an array appears exactly twice except one, which appears once. You must use constant extra space. What is the approach?
Counting Bits, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.
Valid Parenthesis String, from scratch
You have solved this one before. Rebuild it from scratch without looking at your old submission. If the approach does not come back within a few minutes, that is the signal that it needs another pass.