Luhn Checksum

What's being tested

These prompts test checksum implementation, string validation, and bounded combinatorial search around payment-card numbers. Interviewers look for clean isValidLuhn, brand/network rule handling, wildcard completion, and single-digit recovery without brute-forcing unnecessarily.

Patterns & templates

• Luhn checksum — scan right-to-left, double every second digit, subtract 9 if over 9; valid when sum % 10 == 0.

• Check digit derivation — compute partial sum excluding final digit, then check = (10 - partial % 10) % 10; avoid trialing 0..9.

• Network validation — model card brands as {name, lengths, prefixes}; validate digits, length, prefix, then checksum in a predictable order.

• Wildcard enumeration — for small ? counts, DFS over digits; for larger counts, use modulo-DP over positions with state sum_mod_10.

• Counting completions — dynamic program dp[i][mod] in O(n * 10 * choices) time and O(10) space; apply brand constraints first.

• Single-error correction — try replacing each digit with 0..9 except itself, then re-run format and checksum; complexity O(n * 10 * n) naïvely, reducible with precomputed contributions.

• Input hygiene — normalize spaces/dashes only if allowed; otherwise reject non-digits early and keep leading zeros meaningful.

Common pitfalls

Pitfall: Doubling parity is based on distance from the right, not absolute index; parity changes when length changes.

Pitfall: Passing Luhn alone is not enough; a number can satisfy the checksum but fail brand prefix or length rules.

Pitfall: Wildcard brute force explodes at 10^k; switch to modulo counting when k is more than a few digits.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.