Arrays, Strings, and Hashing Questions

Direct answer

Normalize both strings to a canonical Unicode form (NFC: compose combining marks into precomposed characters wherever a composed form exists), then casefold them (a Unicode-aware, more aggressive relative of .lower()), and finally compare character frequency counts using a hash map. Two strings are anagrams exactly when their normalized, casefolded character-count maps are equal. This is O(n) time and O(k) extra space, where k is the number of distinct characters actually present, not the size of the whole alphabet.

Structured elaboration

Why raw codepoint comparison fails on Unicode text. The same visible character can be represented by different codepoint sequences: an accented letter like an e with an acute accent can be one precomposed codepoint, or two codepoints (the base letter plus a separate combining acute-accent mark). Two strings that look identical to a human, and that a user would absolutely expect to be treated as anagrams of each other, can fail a naive character-by-character or Counter-based comparison if one uses the composed form and the other the decomposed form, because they are literally different sequences of codepoints.

Normalization (NFC) before comparison. Running both strings through Unicode Normalization Form C (NFC) converts any decomposed base-plus-combining-mark sequence into its precomposed equivalent wherever one exists, so that two visually-identical strings become byte-for-byte identical at the codepoint level before any counting happens. Normalization must happen before counting, not after, since counting decomposed and precomposed forms separately would treat them as different characters.

Casefolding, not just lowercasing. Python's .casefold() is used instead of .lower() because casefolding is defined specifically for caseless string matching and handles cases .lower() doesn't, most famously the German sharp s (ß), which casefolds to the two-character sequence ss (matching how ß and ss are treated as equivalent in caseless comparisons) while .lower() leaves it unchanged. This means casefolding can change a string's length, which matters for the next step.

Order of operations for the length check. The length check (len(s) != len(t) as a fast rejection before doing full character counting) must be performed on the normalized-and-casefolded strings, never on the raw input, precisely because casefolding can change length. Checking the raw lengths first, as a shortcut before normalization, is a subtle but real bug: it would incorrectly reject valid Unicode-aware anagram pairs whose raw lengths differ only because casefolding expands one of them.

Sorting-based versus counting-based comparison, and the large-alphabet trade-off. A sorting-based approach (sort both normalized/casefolded strings, compare for equality) costs O(n log n) time but only O(1) extra space if sorting can be done on a mutable copy in place (or O(n) if the language's sort isn't in-place), and it never needs a hash map at all, which matters when the character alphabet is enormous, since a sort never allocates space proportional to the alphabet size, only to the string length. A counting-based approach (build a frequency map, compare maps) is O(n) time but pays O(k) space for the map, where k is the number of distinct characters seen; for a small, fixed alphabet like lowercase ASCII, that map is trivially small and counting wins outright on speed, but for full Unicode text (over a million possible codepoints, even though any single string only uses a tiny fraction of them), a hash-map-based counter is still the right call because k is bounded by the input length itself, not by the alphabet size, since a Python dict/Counter only allocates entries for characters that actually appear.

Worked example

Full runnable code with pinned test cases, including the composed-versus-decomposed accented-character case and the German sharp-s casefold case (a genuine subtlety, not a contrived one):

import unicodedata
from collections import Counter


def normalize_for_compare(s):
    """NFC-normalize then casefold. Length check must happen AFTER this,
    never on the raw string (see the STRASSE case below)."""
    return unicodedata.normalize("NFC", s).casefold()


def is_anagram(s, t):
    """O(n) time, O(k) extra space where k is the distinct-character count,
    counting-based rather than sorting-based."""
    s_norm = normalize_for_compare(s)
    t_norm = normalize_for_compare(t)
    if len(s_norm) != len(t_norm):
        return False
    return Counter(s_norm) == Counter(t_norm)


if __name__ == "__main__":
    # Built from explicit codepoint escapes so the composed/decomposed
    # distinction is unambiguous regardless of source-file encoding.
    precomposed = "caf" + "\u00e9"          # c a f e-acute (1 codepoint, U+00E9)
    decomposed = "caf" + "e" + "\u0301"     # c a f e + combining acute (U+0301)

    print("raw codepoint lengths (decomposed vs precomposed):", len(decomposed), len(precomposed))
    print("raw equal (no normalization)?", decomposed == precomposed)
    print("NFC-normalized equal?", unicodedata.normalize("NFC", decomposed) == unicodedata.normalize("NFC", precomposed))

    reordered_precomposed = "\u00e9" + "fac"          # e-acute f a c (reordered anagram)
    strasse_lower = "stra" + "\u00df" + "e"           # stra-sharp_s-e

    tests = [
        ("listen", "silent", True),
        ("Listen", "Silent", True),
        (precomposed, decomposed + "x", False),
        (precomposed, reordered_precomposed, True),
        (decomposed, reordered_precomposed, True),
        ("STRASSE", strasse_lower, True),   # casefold('ss') == casefold('\u00df')
        ("ab", "abc", False),
    ]
    for a, b, expected in tests:
        result = is_anagram(a, b)
        print(f"is_anagram({a!r}, {b!r}) = {result} (expected {expected})")

    print("raw len(strasse_lower) =", len(strasse_lower), " raw len('STRASSE') =", len("STRASSE"))
    print("casefold(strasse_lower) =", strasse_lower.casefold())
    print("casefold('STRASSE') =", "STRASSE".casefold())

Output (actual run):

raw codepoint lengths (decomposed vs precomposed): 5 4
raw equal (no normalization)? False
NFC-normalized equal? True
is_anagram('listen', 'silent') = True (expected True)
is_anagram('Listen', 'Silent') = True (expected True)
is_anagram('café', 'caféx') = False (expected False)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('café', 'éfac') = True (expected True)
is_anagram('STRASSE', 'straße') = True (expected True)
is_anagram('ab', 'abc') = False (expected False)
raw len(strasse_lower) = 6  raw len('STRASSE') = 7
casefold(strasse_lower) = strasse
casefold('STRASSE') = strasse

The STRASSE / straße case is the one to walk through out loud in an interview: the raw strings have different lengths (7 versus 6 codepoints), so a fast-reject on raw length would wrongly report "not an anagram." But ß casefolds to the two characters ss, so both strings casefold to the same 7-character string strasse, and they are correctly identified as an anagram pair. This is exactly why the length check must run on the normalized-and-casefolded strings.

Trade-offs and pitfalls

• Comparing raw strings, or even lowercasing with .lower() instead of .casefold(), silently fails on real internationalized input like the ß/ss case above; .lower() alone leaves ß unchanged and would report STRASSE and straße as not anagrams, which is wrong under Unicode caseless matching rules.
• Checking length before normalizing (a tempting micro-optimization to avoid normalizing strings that "obviously" can't match) is a genuine bug source, not a harmless shortcut, precisely because casefolding and normalization can both change apparent length.
• Sorting-based comparison is the right call when the alphabet is small and fixed (interview-classic lowercase-English anagram checks) since it avoids hash-map overhead entirely; counting-based comparison is the right call once the input might be full Unicode text, since a hash map's cost scales with how many distinct characters actually appear in this particular input, not with the size of the Unicode codepoint space.
• Grapheme-cluster-level correctness (treating an emoji-with-modifier sequence, or a base character plus multiple combining marks, as a single user-perceived "character") is a further layer beyond codepoint-level NFC normalization; this answer normalizes and compares at the codepoint level, which is sufficient for the vast majority of real anagram-style interview questions, but a fully grapheme-aware comparison would need a dedicated segmentation library, which is depth beyond what this question is testing.
• NFC (compose) rather than NFD (decompose) is used here because it produces the more compact, more widely-used-as-a-default form; either would work correctly as long as it's applied consistently to both strings before comparison, since the point is only that both strings land on the same normalized form, not which specific form is chosen.

Direct answer

Treat each value in the array as a pointer: from index i, "follow" nums[i] to land on index nums[i]. Because there are n+1 values all in the range [1, n], at least two different indices must point to the same value (pigeonhole), which means this functional graph has a cycle, and the duplicate value is exactly the entry point of that cycle. Floyd's tortoise-and-hare cycle detection finds that entry point in O(n) time and O(1) extra space, without modifying the array at all, which is exactly what the question asks for.

Approach (Floyd's cycle detection)

1. Start both slow and fast at nums[0], i.e. one step into the implicit linked structure (index 0 always has an outgoing "pointer," but nothing points back to it, so it can't be part of the cycle itself, only the tail leading into it).
2. Advance slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]) each iteration until they meet; a meeting point is guaranteed to exist since the structure has a cycle (standard tortoise-and-hare argument).
3. Reset a second pointer to index 0, then advance it and slow one step at a time together; the index where they meet is the cycle's entry point, which is the duplicate value.

Complexity

Time: O(n) (each phase does at most O(n) steps). Space: O(1) extra; nums itself is never modified.

Edge cases

• Exactly one duplicate value, appearing exactly twice: this is the assumed input shape and the algorithm handles it directly.
• The duplicate value equal to n itself (the largest allowed value): handled the same way, since indexing is 0-based but values start at 1, so nums[i] is always a valid index regardless of which value 1..n is duplicated.

def find_duplicate_floyd(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow2 = 0
    while slow2 != slow:
        slow2 = nums[slow2]
        slow = nums[slow]
    return slow


data = [1, 3, 4, 2, 2]
original = list(data)
print(find_duplicate_floyd(data), data == original)

Output:

2 True

The duplicate is correctly identified as 2, and data == original confirms the array was never mutated during the search.

Alternative technique: index-marking

A second valid approach exploits the same "values are indices" fact differently: walk the array once, and for each value, negate the entry at the index that value points to (abs(value) - 1). If you ever land on an index whose entry is already negative, that index (converted back to 1-based) is the duplicate, because it means two different positions "pointed" to it. This is also O(n) time and O(1) additional space, but unlike Floyd's approach, it works by temporarily mutating nums in place (each visited value's target slot gets negated), so if the caller needs nums to remain externally unmodified while the function runs (not just restored by the time it returns), Floyd's version is the safer default.

def find_duplicate_marking(nums):
    duplicate = None
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            duplicate = idx + 1
            break
        nums[idx] = -nums[idx]
    for i in range(len(nums)):
        nums[i] = abs(nums[i])
    return duplicate


data2 = [1, 3, 4, 2, 2]
print(find_duplicate_marking(data2), data2)

Output:

2 [1, 3, 4, 2, 2]

Both techniques agree on the duplicate (2), and the marking approach restores the array to its original values by the time it returns, even though it mutated it during the scan.

Trade-offs and pitfalls

• "Does not modify the array" has two readings, and the question's phrasing ("without modifying the array") most naturally means Floyd's guarantee: never mutated, at any point, including during execution. The marking approach only satisfies a weaker version ("unmodified once the function returns"), which is a meaningful difference if another thread could read nums concurrently while this function runs, or if the function could throw partway through and leave the array in its negated state.
• A frequent proof gap: candidates often reach for cycle detection without first establishing why a cycle must exist here. The argument is exactly pigeonhole: n+1 values drawn from a range of only n possible values guarantees at least one repeat, and because every value is a valid index (never 0, since the range is [1, n] not [0, n-1]), the "value points to index" structure is well-defined for every position, forcing at least one node in the sequence to be revisited, i.e. a cycle.
• A common bug in the marking approach: forgetting the final restoration pass, which silently corrupts the caller's array (still functionally finds the right duplicate, but violates the "don't modify the array" requirement in a way that's easy to overlook if you only test the return value).

Direct answer

lst[start:stop:step] returns a NEW list built by copying references at indices start, start+step, start+2*step, ... up to but not including stop. Negative indices count from the end (-1 is the last element), and a negative step walks backward. Unlike numpy, Python list slicing always copies, it never returns a view, so a slice of length k from a list of length n costs O(k) time and O(k) extra memory, not O(n).

Structured elaboration

Syntax mechanics. start defaults to 0 (or len(lst) for a negative step), stop defaults to len(lst) (or "through the beginning" for a negative step), step defaults to 1. Negative indices are resolved to positive ones first (-1 -> len(lst) - 1), then the normal start/stop/step machinery applies.

Negative step behavior. A negative step reverses the walk direction. lst[::-1] is the idiomatic full-list reverse; lst[5:1:-2] starts at index 5 and walks backward by 2 until it would reach or pass index 1.

View vs copy. List slicing is always a full copy, a genuinely new list object with its own storage, which is why mutating the slice's result never affects the original list (demonstrated below). This differs from numpy, where basic slicing (not fancy or boolean indexing) returns a VIEW sharing the same underlying buffer, and mutating the view does mutate the source, which is a separate consideration when choosing between the two.

Time and memory complexity. Creating lst[a:b] where b - a = k does exactly k reference copies: O(k) time and O(k) new memory, regardless of how large the source list n is. A common misconception is that slicing costs O(n) because "it touches the whole list": it does not, it only touches the k elements it copies.

Site Reliability Engineering (SRE)-specific danger and alternatives. Repeatedly slicing a large in-memory structure (for example, paginating through a multi-gigabyte log buffer with buf[i:i+chunk] in a loop) duplicates data on every slice, which can double memory pressure or trigger avoidable garbage-collection churn under load, exactly when an SRE (the on-call engineer responsible for a system's reliability) least wants unpredictable memory behavior during an incident. Alternatives that avoid the copy: itertools.islice for a lazy, non-copying iterator over a sequence; a plain generator or yield-based chunker; memoryview for byte-like buffers (bytes, bytearray, array.array), which does support zero-copy sliced views; or, for genuinely huge data, memory-mapping the source (mmap) instead of holding it as a Python list at all.

Worked example

data = [10, 20, 30, 40, 50, 60, 70]  # length n = 7, pinned

print("first three     data[:3]      =", data[:3])
print("last two        data[-2:]     =", data[-2:])
print("every other     data[::2]     =", data[::2])
print("reversed        data[::-1]    =", data[::-1])
print("middle (drop ends) data[1:-1] =", data[1:-1])
print("negative step   data[5:1:-2]  =", data[5:1:-2])

sub = data[1:4]
sub[0] = 999
print("after mutating sub, data      =", data, " (unchanged: slicing copied)")

import sys
n = 100_000
big = list(range(n))
small_slice = big[:10]
print("sys.getsizeof(big)        =", sys.getsizeof(big), "bytes")
print("sys.getsizeof(small_slice)=", sys.getsizeof(small_slice), "bytes")

Output:

first three     data[:3]      = [10, 20, 30]
last two        data[-2:]     = [60, 70]
every other     data[::2]     = [10, 30, 50, 70]
reversed        data[::-1]    = [70, 60, 50, 40, 30, 20, 10]
middle (drop ends) data[1:-1] = [20, 30, 40, 50, 60]
negative step   data[5:1:-2]  = [60, 40]
after mutating sub, data      = [10, 20, 30, 40, 50, 60, 70]  (unchanged: slicing copied)
sys.getsizeof(big)        = 800056 bytes
sys.getsizeof(small_slice)= 136 bytes

The size comparison makes the O(k) claim concrete: a slice of 10 elements from a 100,000-element list costs 136 bytes, not anywhere near the 800,056-byte cost of the full list, confirming the slice's footprint scales with k, not n.

Trade-offs and pitfalls

• Assuming slicing is "free" or O(1): it is O(k), which is cheap for small k but adds up when repeated over large chunks in a hot loop.
• Assuming list slicing returns a view like numpy does: it never does. If zero-copy behavior on a byte buffer is needed, reach for memoryview, not a list.
• Off-by-one errors with a negative step (lst[stop:start:-1]-style mistakes) are the single most common source of "why is my reversed slice missing an element."
• Rebuilding a large structure via repeated slicing inside an incident-response script is exactly the kind of thing that can turn a memory-pressure incident into a self-inflicted one.

Direct answer

Normalize both strings the same way (lowercase, drop non-alphanumeric characters), then compare their character frequency counts. Building a frequency map is a single O(n) pass per string; sorting both normalized strings and comparing them is O(n log n). For long strings that gap is the entire reason to prefer the frequency map.

Structured elaboration

Normalizing. Filter each string down to lowercase alphanumeric characters only (c.isalnum()), dropping spaces and punctuation. This is a modeling decision worth stating out loud: taken completely literally, "Dormitory" and "dirty room" are not the same sequence of characters at all (different case, an extra space), the question's own instruction to ignore case and non-alphanumeric characters is what licenses treating them as equivalent.

Frequency map. Count occurrences of each normalized character in both strings (collections.Counter does this in one pass) and compare the two counts for equality. Two strings are anagrams exactly when every distinct character occurs the same number of times in both, which a Counter equality check verifies directly, in O(k) time to compare, where k is the number of distinct normalized characters, bounded by the alphabet rather than by n.

Sorting alternative. Sort both normalized character sequences and check they are identical; two strings are anagrams if and only if their sorted forms match. Correct, but O(n log n) because of the sort, versus O(n) for building and comparing frequency maps. For long strings, that difference in growth rate is exactly what "preferred... for long strings" is asking you to justify.

Cheap short-circuit. Compare lengths of the two normalized sequences first; a mismatch there proves non-anagram in O(1) (after the O(n) normalization pass), without needing to build either a sorted copy or a frequency map.

Worked example

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    def normalize(x: str):
        return [c.lower() for c in x if c.isalnum()]
    ns, nt = normalize(s), normalize(t)
    if len(ns) != len(nt):
        return False
    return Counter(ns) == Counter(nt)

from collections import Counter as _Counter

def _is_anagram_sorted_check(s, t):
    def normalize(x):
        return sorted(c.lower() for c in x if c.isalnum())
    return normalize(s) == normalize(t)

cases = [
    ("Dormitory", "Dirty Room", True),
    ("William Shakespeare", "I am a weakish speller", True),
    ("listen", "silent", True),
    ("hello", "world", False),
    ("A gentleman", "Elegant man", True),
    ("", "", True),
    ("a", "ab", False),
]
all_agree = True
for a, b, expected in cases:
    r = is_anagram(a, b)
    print(f"is_anagram({a!r}, {b!r}) = {r} (expected {expected})")
    if r != _is_anagram_sorted_check(a, b):
        all_agree = False
print()
print("all cases agree between frequency-map and sorting approaches, as expected."
      if all_agree else "MISMATCH between frequency-map and sorting approaches!")

Output:

is_anagram('Dormitory', 'Dirty Room') = True (expected True)
is_anagram('William Shakespeare', 'I am a weakish speller') = True (expected True)
is_anagram('listen', 'silent') = True (expected True)
is_anagram('hello', 'world') = False (expected False)
is_anagram('A gentleman', 'Elegant man') = True (expected True)
is_anagram('', '') = True (expected True)
is_anagram('a', 'ab') = False (expected False)

all cases agree between frequency-map and sorting approaches, as expected.

Every case, including the classic "William Shakespeare" / "I am a weakish speller" anagram and the empty-string edge case, matches expectation, and a parallel sorting-based implementation was run against the identical inputs and agreed with the frequency-map result on every one, confirming the two approaches are equivalent in correctness, differing only in complexity.

Trade-offs and pitfalls

Check the length mismatch before doing anything else; it is the cheapest possible rejection and avoids building a data structure you already know cannot match.

Sorting is still a reasonable, sometimes preferable, choice for very short strings, or when you need the sorted form anyway for something else (grouping many words by their sorted key, for instance): at small n, the constant-factor difference between O(n) and O(n log n) barely matters in practice, and the sorted form doubles as a canonical grouping key.

Stating your normalization rules explicitly is part of a senior answer here: "ignore case and non-alphanumeric characters" is a specific, narrower definition of anagram than the literal character-for-character one, and silently assuming it without saying so is a common way this question goes subtly wrong in an interview, even when the code itself is correct.

Direct answer

Compare the sum (and sum of squares) of the actual array against what a clean 1..n sequence would sum to; the two differences give you a system of two equations in the two unknowns (the missing value and the duplicate value), which you can solve directly. That approach is O(n) time and O(1) space, but it is vulnerable to integer overflow in fixed-width-integer languages, so a bitwise XOR-based approach is the more robust choice when overflow safety matters, at the cost of being noticeably less intuitive to derive on the spot.

Approach: sum and sum-of-squares

Let missing and dup be the two unknowns. Two quantities are cheap to compute from the array:

Dividing the second equation by the first isolates the other combination:

Now sum_diff gives missing - dup directly, and the division above gives missing + dup; adding and subtracting those two values solves for missing and dup individually.

Approach: XOR

1. XOR every value 1..n together with every value in nums. Every value that appears exactly twice (every correct value except missing and dup) cancels itself out via x ^ x == 0; missing (present once, from the 1..n side only) and dup (present three times total: twice in nums, once from the 1..n side, an odd count) survive, leaving missing ^ dup.
2. Find any bit where missing and dup differ (any set bit in missing ^ dup; the lowest set bit is a convenient, deterministic choice).
3. Partition both the 1..n range and nums by that bit, XOR each partition together; this isolates missing and dup into two separate accumulators (in some order).
4. One more pass, checking whether one of the two candidates actually occurs in nums, resolves which candidate is dup and which is missing.

Complexity

Both approaches: O(n) time, O(1) extra space. The sum approach is easier to derive but risks overflow on the squares term for large n in a fixed-width-integer language; the XOR approach never accumulates a value wider than the input values themselves, so it cannot overflow regardless of n.

Edge cases

• missing and dup adjacent in value (e.g. missing=3, dup=2): both approaches handle this with no special-casing.
• n = 1 isn't meaningfully defined for this problem (can't have both a missing and a duplicate value with a single slot), so this assumes n >= 2.

def missing_and_duplicate_sum(nums):
    n = len(nums)
    expected_sum = n * (n + 1) // 2
    expected_sqsum = n * (n + 1) * (2 * n + 1) // 6
    actual_sum = sum(nums)
    actual_sqsum = sum(x * x for x in nums)

    sum_diff = expected_sum - actual_sum
    sqsum_diff = expected_sqsum - actual_sqsum

    sum_plus = sqsum_diff // sum_diff
    missing = (sum_diff + sum_plus) // 2
    dup = sum_plus - missing
    return missing, dup


def missing_and_duplicate_xor(nums):
    n = len(nums)
    xor_all = 0
    for i in range(1, n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    diff_bit = xor_all & (-xor_all)

    group_a = 0
    group_b = 0
    for i in range(1, n + 1):
        if i & diff_bit:
            group_a ^= i
        else:
            group_b ^= i
    for num in nums:
        if num & diff_bit:
            group_a ^= num
        else:
            group_b ^= num
    if nums.count(group_a) > 0:
        dup, missing = group_a, group_b
    else:
        dup, missing = group_b, group_a
    return missing, dup


nums = [1, 2, 2, 4]  # n=4; 3 is missing, 2 is duplicated
print(missing_and_duplicate_sum(nums))
print(missing_and_duplicate_xor(nums))

nums2 = [3, 1, 2, 5, 3]  # n=5; 4 is missing, 3 is duplicated
print(missing_and_duplicate_sum(nums2))
print(missing_and_duplicate_xor(nums2))

Output:

(3, 2)
(3, 2)
(4, 3)
(4, 3)

Both approaches agree on both test cases: (missing, dup) = (3, 2) for [1, 2, 2, 4], and (4, 3) for [3, 1, 2, 5, 3], confirming the algebra and the bitwise derivation independently reach the same answer.

Trade-offs and pitfalls

• Numerical stability (overflow), the question's specific ask: expected_sqsum grows roughly like $n^3/3$, so for large n (say, n around $10^9$ or larger, plausible for an ID-space-sized array) this can overflow a 32-bit or even 64-bit signed integer in a language with fixed-width arithmetic (C, C++, Java, Rust's default integer types), silently producing a wrong sqsum_diff and therefore a wrong answer with no error raised. Python itself has arbitrary-precision integers, so this specific overflow can't happen in Python, but a candidate should still name it, since the same algorithm is routinely implemented in fixed-width-integer languages, and "no overflow in Python" is not the same claim as "no overflow, period."
• The XOR approach sidesteps overflow entirely, since XOR never produces a value wider than the bit-width of the inputs themselves (unlike a running sum or sum-of-squares, which can grow arbitrarily large as more terms accumulate); this is the practical reason to prefer it once overflow is a real concern, at the cost of the derivation being considerably less obvious to reconstruct under interview pressure than "add up the differences."
• A common bug in the sum approach: using floating-point division for sum_plus, which can introduce rounding error for large n; integer division (//) is correct here because sqsum_diff is guaranteed to be evenly divisible by sum_diff (their ratio is missing + dup, an integer), so floor division is exact, not an approximation.
• A common bug in the XOR approach: picking the wrong bit to partition on (any set bit in missing ^ dup works, not just the lowest one, but it must be a bit where they actually differ), or forgetting the final disambiguation pass and returning (group_a, group_b) in an arbitrary, unverified order.