A twin-booster rocket has a left booster and a right booster, each configured with its own ignition code: a non-negative integer whose binary representation marks which fuel valves are primed (a 1 bit means that valve is primed). Mission control treats a valve as primed overall if EITHER booster has that valve primed — that is, the combined ignition pattern is the bitwise OR of the two booster codes.
Before launch, mission control has a required combined pattern that this bitwise OR must match exactly. You may toggle any single bit (turning a 0 into a 1, or a 1 into a 0) in either booster's code; each toggle is one operation, and any number of toggles may be applied to either code. Determine the minimum number of toggles needed, across both codes combined, so that the bitwise OR of the (possibly modified) left and right codes equals the required pattern exactly.
A single line containing three space-separated non-negative integers: left, right, target — the left booster code, the right booster code, and the required combined pattern.
A single integer: the minimum number of bit toggles needed.
Example 1
Input
1 3 6
Expected
3
Explanation
In binary, left = 0001, right = 0011, target = 0110. At bit value 1: both codes have this bit set, but the target does not want it, so both bits must be toggled off (2 toggles). At bit value 2: neither code has this bit set, but the target wants it, so one of the two codes must have this bit toggled on (1 toggle). At bit value 4: neither code has it and the target does not want it either, so no change is needed. The total is 2 + 1 = 3 toggles.
Example 2
Input
0 0 15
Expected
4
Explanation
Both booster codes start at 0, so their OR is 0, while the target 15 (binary 1111) requires all four of the lowest bits to be set. For each of those four bit positions, neither code currently has the bit set, so exactly one toggle (on either code) is needed to set it there. That gives 4 toggles in total, and no arrangement can do better since all four bits must be turned on from scratch.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →