Greedy algorithms and bit manipulation

Two small topics that appear often enough to be worth a file. Greedy is about justifying a choice; bits are about recognising a handful of tricks.

Greedy

Take the locally best option and never reconsider. Fast and simple when it works — and confidently wrong when it doesn’t.

The question that matters: why is greedy correct here? Producing a greedy solution without justifying it is the weak version of the answer.

Two properties must hold:

• Greedy choice property — a locally optimal choice is part of some globally optimal solution.
• Optimal substructure — an optimal solution contains optimal solutions to subproblems.

The standard justification is an exchange argument: take any optimal solution, show you can swap in the greedy choice without making it worse, therefore a greedy solution is optimal.

Where greedy works

Where it fails

0/1 knapsack. Highest value/weight first is wrong when you can’t take fractions:

capacity 10
A: weight 6, value 30   (ratio 5.0)
B: weight 5, value 24   (ratio 4.8)
C: weight 5, value 24   (ratio 4.8)

greedy -> A only        = 30
optimal -> B + C        = 48

Greedy commits to A and then can’t fit anything else. Needs DP — see ../06_dp/02_knapsack_lcs_edit_distance.md.

Coin change with arbitrary denominations. Greedy works for standard currencies and fails for [1, 3, 4] making 6: greedy gives 4+1+1 (three coins), optimal is 3+3 (two).

That coin example is the cleanest way to show you understand greedy’s limits, and it’s short enough to state from memory.

The heuristic: if the problem asks for an optimum and choices interact, suspect DP. If a simple ordering makes each choice independent, suspect greedy — then justify it.

Bit manipulation

x & 1          # 1 if odd
x >> 1         # divide by 2 (floor for non-negative)
x << 1         # multiply by 2
x & (x - 1)    # clear the lowest set bit
x & -x         # ISOLATE the lowest set bit
x ^ y          # differing bits
~x             # bitwise NOT (in Python: -x - 1)

The two worth memorising are x & (x - 1) and x & -x. Almost every bit puzzle uses one of them.

Counting set bits

def count_bits(x: int) -> int:
    count = 0
    while x:
        x &= x - 1          # clears the lowest set bit each iteration
        count += 1
    return count

x.bit_count()               # Python 3.10+ — just use this

Brian Kernighan’s method runs in O(set bits) rather than O(total bits). Python 3.10 added int.bit_count(), so know the trick and use the builtin.

XOR properties

The three that solve most XOR problems:

x ^ x = 0
x ^ 0 = x
XOR is commutative and associative

Single number — every element appears twice except one:

from functools import reduce
import operator

def single_number(nums: list[int]) -> int:
    return reduce(operator.xor, nums)      # pairs cancel, the loner survives

O(n) time, O(1) space, and it beats the hash-set solution on space. Elegant enough to be worth recognising instantly.

Two single numbers — everything else appears twice:

def two_singles(nums: list[int]) -> tuple[int, int]:
    xor_all = reduce(operator.xor, nums)   # = a ^ b
    bit = xor_all & -xor_all               # any bit where a and b differ
    a = reduce(operator.xor, (n for n in nums if n & bit))
    return a, a ^ xor_all

Partition by a differing bit, so each group contains exactly one of the two singles. This uses both key tricks together.

Subsets via bitmasks

def subsets(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    return [[nums[i] for i in range(n) if mask >> i & 1]
            for mask in range(1 << n)]

Each of the 2^n masks encodes one subset. Also the basis of bitmask DP — travelling salesman, assignment problems — where the state is a set of visited items packed into an integer.

Python specifics worth knowing

• Integers are arbitrary precision, so there’s no overflow and no fixed width. Tricks assuming 32-bit wraparound don’t translate directly.
• ~x is -x - 1, not a 32-bit complement. Mask with & 0xFFFFFFFF if you need fixed-width behaviour.
• Negative numbers behave as infinite two’s complement, so -1 >> 1 is -1, not 0.

That first point catches people porting solutions from C++ or Java.

Interview angle

• “When is greedy correct?” — when the greedy choice property and optimal substructure hold. Justify with an exchange argument: any optimal solution can be modified to include the greedy choice without getting worse.
• “Give an example where greedy fails.” — coin change with [1, 3, 4] making 6: greedy takes 4+1+1, optimal is 3+3. Or 0/1 knapsack, where the best ratio item can block two better ones.
• “Greedy or DP?” — if a simple ordering makes each choice independent of the rest, greedy. If choices interact so that taking one closes off better combinations, DP.
• “What does x & (x - 1) do?” — clears the lowest set bit. Repeatedly applying it counts set bits in O(set bits). x & -x isolates that bit instead, which is how you partition by a differing bit.
• “Find the element appearing once when all others appear twice.” — XOR everything. Pairs cancel to zero and the loner survives. O(n) time and O(1) space, better than a hash set.
• “Anything different about bit manipulation in Python?” — integers are arbitrary precision, so there’s no overflow and ~x is -x - 1 rather than a 32-bit complement. Mask explicitly if you need fixed-width semantics.