Constraints

• 0 <= len(card_number) <= 32
• card_number may contain digits or other characters
• A valid VISA number must be exactly 16 characters, all digits, and start with 4

Examples

Solution

def solution(card_number):
    def luhn_valid(s):
        total = 0
        should_double = False
        for ch in reversed(s):
            digit = ord(ch) - ord('0')
            if should_double:
                digit *= 2
                if digit > 9:
                    digit -= 9
            total += digit
            should_double = not should_double
        return total % 10 == 0

    if len(card_number) != 16:
        return False
    if not card_number.isdigit():
        return False
    if not card_number.startswith('4'):
        return False
    return luhn_valid(card_number)

Time complexity: O(n), where n is the length of card_number. Space complexity: O(1).

Hints

1. For Luhn, process digits from right to left and double every second digit.
2. If a doubled digit becomes greater than 9, subtract 9 from it before adding to the checksum.

Constraints

• 0 <= len(card_number) <= 32
• card_number may contain digits or other characters
• Network matching is based on exact length and prefix
• Checksum is evaluated only after a supported network pattern is matched

Examples

Solution

def solution(card_number):
    def luhn_valid(s):
        total = 0
        should_double = False
        for ch in reversed(s):
            digit = ord(ch) - ord('0')
            if should_double:
                digit *= 2
                if digit > 9:
                    digit -= 9
            total += digit
            should_double = not should_double
        return total % 10 == 0

    def detect_network(s):
        if not s.isdigit():
            return None
        if len(s) == 16:
            if s[0] == '4':
                return 'VISA'
            if s[:2] in {'51', '52', '53', '54', '55'}:
                return 'MASTERCARD'
        if len(s) == 15 and s[:2] in {'34', '37'}:
            return 'AMEX'
        return None

    network = detect_network(card_number)
    if network is None:
        return 'UNKNOWN_NETWORK'
    if not luhn_valid(card_number):
        return 'INVALID_CHECKSUM'
    return network

Time complexity: O(n), where n is the length of card_number. Space complexity: O(1).

Hints

1. Separate the network-detection logic from the Luhn checksum logic.
2. If a number has an unsupported length or prefix, do not run checksum-based classification; return UNKNOWN_NETWORK.

Constraints

• 1 <= len(redacted) <= 16
• redacted contains only digits and * characters
• 1 <= number of * characters <= 5
• Supported networks use the same length, prefix, and Luhn rules as Part 2

Examples

Solution

def solution(redacted):
    from itertools import product

    network_names = ['AMEX', 'MASTERCARD', 'VISA']
    counts = {name: 0 for name in network_names}

    def luhn_valid(s):
        total = 0
        should_double = False
        for ch in reversed(s):
            digit = ord(ch) - ord('0')
            if should_double:
                digit *= 2
                if digit > 9:
                    digit -= 9
            total += digit
            should_double = not should_double
        return total % 10 == 0

    def detect_network(s):
        if not s.isdigit():
            return None
        if len(s) == 16:
            if s[0] == '4':
                return 'VISA'
            if s[:2] in {'51', '52', '53', '54', '55'}:
                return 'MASTERCARD'
        if len(s) == 15 and s[:2] in {'34', '37'}:
            return 'AMEX'
        return None

    wildcard_positions = []
    chars = list(redacted)
    for i, ch in enumerate(chars):
        if ch == '*':
            wildcard_positions.append(i)

    for replacement in product('0123456789', repeat=len(wildcard_positions)):
        for pos, digit in zip(wildcard_positions, replacement):
            chars[pos] = digit
        candidate = ''.join(chars)
        network = detect_network(candidate)
        if network is not None and luhn_valid(candidate):
            counts[network] += 1

    return [[name, counts[name]] for name in network_names]

Time complexity: O(10^w * n), where w is the number of wildcards and n is the string length. Space complexity: O(n), excluding the returned output.

Hints

1. With at most 5 wildcards, there are at most 100000 completions, which is small enough to enumerate directly.
2. After filling the wildcards, reuse the same network-detection and Luhn validation steps.

Constraints

• 1 <= len(corrupted) <= 17
• corrupted ends with ?
• All characters before ? are digits
• The observed number length is expected to be 15 or 16 for recoverable cards
• For a digit-change error, the original digit must be different from the observed digit
• For an adjacent-swap error, the swap must change the observed string, so equal adjacent digits do not generate a candidate

Examples

Solution

def solution(corrupted):
    if not corrupted.endswith('?'):
        return []

    observed = corrupted[:-1]
    if not observed.isdigit():
        return []

    def luhn_valid(s):
        total = 0
        should_double = False
        for ch in reversed(s):
            digit = ord(ch) - ord('0')
            if should_double:
                digit *= 2
                if digit > 9:
                    digit -= 9
            total += digit
            should_double = not should_double
        return total % 10 == 0

    def detect_network(s):
        if not s.isdigit():
            return None
        if len(s) == 16:
            if s[0] == '4':
                return 'VISA'
            if s[:2] in {'51', '52', '53', '54', '55'}:
                return 'MASTERCARD'
        if len(s) == 15 and s[:2] in {'34', '37'}:
            return 'AMEX'
        return None

    found = {}

    def add_if_valid(candidate):
        network = detect_network(candidate)
        if network is not None and luhn_valid(candidate):
            found[candidate] = network

    n = len(observed)

    for i in range(n):
        original_digit = observed[i]
        for digit in '0123456789':
            if digit == original_digit:
                continue
            candidate = observed[:i] + digit + observed[i + 1:]
            add_if_valid(candidate)

    for i in range(n - 1):
        if observed[i] == observed[i + 1]:
            continue
        chars = list(observed)
        chars[i], chars[i + 1] = chars[i + 1], chars[i]
        candidate = ''.join(chars)
        add_if_valid(candidate)

    return [[number, found[number]] for number in sorted(found, key=lambda x: int(x))]

Time complexity: O(n^2), because O(n) candidates are generated and each validation/candidate construction costs O(n). Space complexity: O(n), excluding the returned output.

Hints

1. Generate candidates by trying every single-position digit replacement and every adjacent swap, then validate each candidate.
2. Use a set or dictionary to avoid returning the same valid original more than once.