Get started

Bitmask Coding Problems: 7 Questions with Solutions

7 bitmask coding problems — 1 medium · 6 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 4-day plan.

  • Problems: 7
  • By difficulty: 1 medium · 6 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

A bitmask uses the bits of one integer as a set of small items: bit i is on when item i is chosen, used or visited. With at most 15 or 20 items every subset is a number below 2ⁿ, so it can index an array, and dynamic programming over subsets — which tasks are done, which nodes have been visited, which primes a product already contains — becomes a table of 2ⁿ entries. The problems here practise that table, the bit operations that move from one subset to the next, and spotting the small bound that makes it affordable.

How bitmask works, step by step

nums351bit 0bit 1bit 2sum00000013010501181001101411061119sum = 6: mask 110 = {5, 1}
Every subset's sum from a smaller subset, with bitmask DP. Example: nums = [3, 5, 1]; which subsets sum to 6?
  1. Each subset of [3, 5, 1] is a 3-bit mask: bit j, counted from the right, set means nums[j] is in, and mask 000 is the empty set with sum 0. Clearing a mask's lowest set bit, mask & (mask − 1), gives a smaller mask, which is already done.
  2. mask 001 = {3}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 000, the empty set, already known to sum to 0. So sum[001] = 0 + 3 = 3. One addition per mask, never a loop over the bits.
  3. mask 010 = {5}: its lowest set bit is bit 1 (nums[1] = 5), and without it the mask is 000, the empty set, already known to sum to 0. So sum[010] = 0 + 5 = 5. A single-bit mask always comes from 000.
  4. mask 011 = {3, 5}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 010, {5}, already known to sum to 5. So sum[011] = 5 + 3 = 8.
  5. mask 100 = {1}: its lowest set bit is bit 2 (nums[2] = 1), and without it the mask is 000, the empty set, already known to sum to 0. So sum[100] = 0 + 1 = 1. Going through the masks in increasing order is what makes this safe: mask & (mask − 1) is always smaller, so it is always done.
  6. mask 101 = {3, 1}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 100, {1}, already known to sum to 1. So sum[101] = 1 + 3 = 4.
  7. mask 110 = {5, 1}: its lowest set bit is bit 1 (nums[1] = 5), and without it the mask is 100, {1}, already known to sum to 1. So sum[110] = 1 + 5 = 6.
  8. mask 111 = {3, 5, 1}: its lowest set bit is bit 0 (nums[0] = 3), and without it the mask is 110, {5, 1}, already known to sum to 6. So sum[111] = 6 + 3 = 9. The last mask, the whole set, reuses 110 like every other.
  9. All 8 subset sums came from one addition each: O(2ⁿ), not O(n·2ⁿ) for re-adding every subset. Any question about subsets is now a lookup: 110 = {5, 1} is the only one summing to 6.

Bitmask study plan

4 of the 7 Bitmask problems (1 medium and 3 hard) over 4 days, about 3 h 20 min in all — the pattern first, then easiest to hardest. After that, the other 3 in the full list below are practice at your own pace. Then move on to Number Theory.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Day 3

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Day 4

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

Next topic: Number Theory

Bitmask: the essentials

When to reach for it

One dimension is tiny — up to 20 tasks, nodes or slots, the ten primes below 30, a grid five cells wide — and what matters is which items are used, not their order: "assign every task", "visit every node". 2²⁰ is about a million states; much beyond 20 items, look elsewhere.

The pattern

Let dp[mask] be the best result using exactly the items in mask. A transition adds an item (mask | (1 << i)) or a submask; increasing mask order works, as setting a bit makes the number larger. A walk through every node must also know where it is: the state is (mask, last item). Bit basics are on Bit Manipulation.

def min_sessions(tasks, limit):         # fewest sessions of at most limit hours
    n = len(tasks)
    best = [(n + 1, 0)] * (1 << n)      # best[mask]: (sessions, hours in the last one)
    best[0] = (1, 0)
    for mask in range(1 << n):
        s, used = best[mask]
        for i, t in enumerate(tasks):
            if not mask & (1 << i):     # task i is not done yet
                nxt = (s, used + t) if used + t <= limit else (s + 1, t)
                best[mask | (1 << i)] = min(best[mask | (1 << i)], nxt)
    return best[-1][0]

Cost

O(2ⁿ × n) time and O(2ⁿ) space when each transition adds one item. Looping over every submask of every mask is O(3ⁿ), about 1.4 × 10⁷ for n = 15. A last item in the state multiplies both by n.

Common mistakes

  • A state missing what the future needs: a walk through every node needs the current node too.
  • Starting entries at 0 in a minimisation, so impossible subsets look free; start at infinity.
  • The submask loop sub = (sub - 1) & mask ends at 0: handle the empty submask apart, or it is skipped or never stops.
  • One bit per slot when a slot holds two items; use two bits, or base 3.

Start with

All bitmask problems

Medium (1)

Hard (6)

Companies that ask bitmask problems

Next topic: Number Theory