17. Greedy and Bit Manipulation

Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. When it works, greedy is simpler and faster than DP. Bit manipulation uses binary representation to solve problems with O(1) operations that would otherwise require loops or extra space.

When Greedy Works

Greedy works when the greedy choice property holds: making the best local choice at each step produces the best global result. You can't always prove this easily — but there are well-known problem families where greedy is guaranteed to work.

Greedy works for:

• Interval scheduling (activity selection)
• Huffman coding
• Fractional knapsack
• Minimum coins with canonical denominations (US coins)
• Dijkstra's algorithm (it's greedy!)
• MST algorithms (Kruskal's, Prim's)

Greedy fails for:

• 0/1 knapsack → need DP
• Coin change with arbitrary denominations → need DP
• Longest path in general graphs → NP-hard

NP-hard means no known algorithm solves it in polynomial time (O(n²), O(n³), etc.). NP stands for Nondeterministic Polynomial — a complexity class. NP-hard problems are at least as hard as the hardest problems in NP. In practice: don't look for an efficient algorithm, use approximations or restrict the input (e.g., longest path in a DAG is solvable in O(V+E) via topological sort).

Pattern: Interval Scheduling

Given intervals, find the maximum number of non-overlapping intervals. Greedy: always pick the interval that ends earliest.

LeetCode 435 - Non-overlapping Intervals

def max_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])  # sort by end time
    count = 1
    end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] >= end:  # no overlap
            count += 1
            end = intervals[i][1]
    return count

Why it works: picking the earliest-ending interval leaves the most room for future intervals. Any other choice can only do worse.

Pattern: Merge Intervals

Given overlapping intervals, merge them into non-overlapping intervals.

LeetCode 56 - Merge Intervals

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort()
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:  # overlap
            merged[-1][1] = max(merged[-1][1], end)  # extend
        else:
            merged.append([start, end])
    return merged

Sort by start, then greedily extend or start new intervals. O(n log n) for the sort.

Pattern: Jump Game

Can you reach the last index if each element tells you the max jump length?

LeetCode 55 - Jump Game

def can_jump(nums: list[int]) -> bool:
    max_reach = 0
    for i in range(len(nums)):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
    return True

Greedy: track the farthest position you can reach. If your current index exceeds max_reach, you're stuck.

Greedy vs DP — How to Decide

Ask: "If I make the locally best choice, can a later choice make it suboptimal?"

• No → greedy works. Example: interval scheduling — picking earliest end never hurts.
• Yes → need DP. Example: coin change with coins [1, 3, 4] and target 6. Greedy picks 4+1+1=3 coins. DP finds 3+3=2 coins.

When in doubt, try greedy first (it's simpler). If you find a counterexample, switch to DP.

Bit Manipulation

Computers store numbers in binary. Bit operations work on individual bits in O(1) — no loops needed.

Essential Operations

# AND — both bits must be 1
5 & 3   # 101 & 011 = 001 = 1

# OR — either bit is 1
5 | 3   # 101 | 011 = 111 = 7

# XOR — bits must differ
5 ^ 3   # 101 ^ 011 = 110 = 6

# NOT — flip all bits (Python uses ~ which gives -(n+1))
~5      # -6  (Python integers have unlimited width)

# Left shift — multiply by 2
5 << 1  # 101 << 1 = 1010 = 10

# Right shift — divide by 2
5 >> 1  # 101 >> 1 = 10 = 2

XOR Properties

XOR is the most useful bit operation for DSA:

a ^ a == 0     # anything XOR itself is 0
a ^ 0 == a     # anything XOR 0 is itself
a ^ b ^ a == b # XOR is self-inverse (order doesn't matter)

This gives you a powerful trick: XOR all elements, duplicates cancel out.

LeetCode 136 - Single Number

# Find the single number (all others appear twice) — O(n) time, O(1) space
def single_number(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result

Without XOR, you'd need a hash set (O(n) space) or sorting (O(n log n) time).

Python one-liner using reduce:

from functools import reduce
from operator import xor

def single_number(nums: list[int]) -> int:
    return reduce(xor, nums)

Common Bit Tricks

# Check if n is a power of 2
def is_power_of_two(n: int) -> bool:
    return n > 0 and n & (n - 1) == 0

# Count set bits (number of 1s)
def count_bits(n: int) -> int:
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Python built-in alternative
bin(n).count('1')

# Get the ith bit
def get_bit(n: int, i: int) -> int:
    return (n >> i) & 1

# Set the ith bit
def set_bit(n: int, i: int) -> int:
    return n | (1 << i)

# Clear the ith bit
def clear_bit(n: int, i: int) -> int:
    return n & ~(1 << i)

Bitmask as Set

Use an integer as a set of flags. Bit i is 1 if element i is in the set. Gives O(1) add, remove, and membership — for sets up to 64 elements (or unlimited in Python, since integers have arbitrary precision).

# Subset representation with bitmask
mask = 0
mask |= (1 << 3)   # add element 3
mask |= (1 << 5)   # add element 5
mask &= ~(1 << 3)  # remove element 3

# Check membership
if mask & (1 << 5):
    print("5 is in the set")

# Iterate all subsets of {0, 1, ..., n-1}
for mask in range(1 << n):
    # mask represents one subset
    pass

This is used in bitmask DP — when the state is "which elements have been used."

When to Use Bit Manipulation

• Finding unique elements (XOR cancels duplicates)
• Power-of-2 checks
• Compact set representation (bitmask DP)
• Low-level optimization (multiply/divide by 2)
• Permission systems (read=4, write=2, execute=1)

Practice Problems

Key Takeaways

• Greedy makes the locally optimal choice — works when local optimality guarantees global optimality
• Interval problems (scheduling, merging) are the classic greedy family
• If greedy fails (counterexample exists), fall back to DP
• XOR is the key bit operation: a^a=0, a^0=a — finds unique elements in O(1) space
• Bitmasks represent sets as integers — O(1) operations, unlimited width in Python
• Bit tricks: power-of-2 check (n&(n-1)==0), count bits, get/set/clear individual bits
• Python's bin(n).count('1') is a handy built-in for counting set bits
• Greedy is O(n) or O(n log n). Bit operations are O(1). Both are faster than DP when applicable