Constraints

• Treat the input as a string.
• A valid VISA candidate for this part has exactly 16 digits and starts with '4'.
• Any non-digit input, wrong length, or wrong prefix should be treated as invalid.
• Use the Luhn checksum exactly as specified.

Examples

Solution

def solution(card):
    def luhn(num):
        total = 0
        double = False
        for ch in reversed(num):
            d = ord(ch) - 48
            if double:
                d *= 2
                if d > 9:
                    d -= 9
            total += d
            double = not double
        return total % 10 == 0

    if not isinstance(card, str):
        return 'INVALID_CHECKSUM'
    if len(card) != 16 or not card.isdigit() or card[0] != '4':
        return 'INVALID_CHECKSUM'
    return 'VISA' if luhn(card) else 'INVALID_CHECKSUM'

Time complexity: O(n), where n is the card length (here n = 16).. Space complexity: O(1).

Hints

1. Traverse the number from right to left and alternate whether a digit is doubled.
2. When doubling a digit produces a number greater than 9, subtract 9 from it.

Constraints

• Treat the input as a string.
• Supported networks: VISA = 16 digits starting with '4'; MASTERCARD = 16 digits starting with 51-55; AMEX = 15 digits starting with 34 or 37.
• If prefix/length do not match any supported network, return 'UNKNOWN_NETWORK'.
• If prefix/length match a supported network but Luhn fails, return 'INVALID_CHECKSUM'.

Examples

Solution

def solution(card):
    def luhn(num):
        total = 0
        double = False
        for ch in reversed(num):
            d = ord(ch) - 48
            if double:
                d *= 2
                if d > 9:
                    d -= 9
            total += d
            double = not double
        return total % 10 == 0

    def classify(num):
        if len(num) == 16 and num.startswith('4'):
            return 'VISA'
        if len(num) == 16 and num[:2].isdigit() and 51 <= int(num[:2]) <= 55:
            return 'MASTERCARD'
        if len(num) == 15 and num[:2] in ('34', '37'):
            return 'AMEX'
        return None

    if not isinstance(card, str) or not card.isdigit():
        return 'UNKNOWN_NETWORK'

    network = classify(card)
    if network is None:
        return 'UNKNOWN_NETWORK'
    return network if luhn(card) else 'INVALID_CHECKSUM'

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

Hints

1. Separate the problem into two steps: identify the network by prefix/length, then run Luhn only on supported candidates.
2. Because the network rules are disjoint here, at most one network can match a given input.

Constraints

• Treat the input as a string.
• The input may contain digits and '*' only.
• There are at most 5 '*' characters.
• Only lengths 15 and 16 can match supported networks; all other lengths return an empty list.

Examples

Solution

def solution(card):
    def luhn(num):
        total = 0
        double = False
        for ch in reversed(num):
            d = ord(ch) - 48
            if double:
                d *= 2
                if d > 9:
                    d -= 9
            total += d
            double = not double
        return total % 10 == 0

    def classify(num):
        if len(num) == 16 and num.startswith('4'):
            return 'VISA'
        if len(num) == 16 and 51 <= int(num[:2]) <= 55:
            return 'MASTERCARD'
        if len(num) == 15 and num[:2] in ('34', '37'):
            return 'AMEX'
        return None

    def prefix_compatible(pattern, prefixes):
        for prefix in prefixes:
            ok = True
            for i, ch in enumerate(prefix):
                if pattern[i] != '*' and pattern[i] != ch:
                    ok = False
                    break
            if ok:
                return True
        return False

    if not isinstance(card, str):
        return []
    if len(card) not in (15, 16):
        return []
    if any(ch not in '0123456789*' for ch in card):
        return []
    if card.count('*') > 5:
        return []

    networks = {
        'AMEX': {'length': 15, 'prefixes': ['34', '37']},
        'MASTERCARD': {'length': 16, 'prefixes': ['51', '52', '53', '54', '55']},
        'VISA': {'length': 16, 'prefixes': ['4']},
    }

    possible = []
    for name, rules in networks.items():
        if len(card) == rules['length'] and prefix_compatible(card, rules['prefixes']):
            possible.append(name)
    if not possible:
        return []

    chars = list(card)
    star_positions = [i for i, ch in enumerate(chars) if ch == '*']
    counts = {name: 0 for name in possible}

    def any_prefix_still_possible():
        pattern = ''.join(chars)
        for name in possible:
            if prefix_compatible(pattern, networks[name]['prefixes']):
                return True
        return False

    def dfs(idx):
        if idx == len(star_positions):
            num = ''.join(chars)
            net = classify(num)
            if net is not None and luhn(num):
                counts[net] += 1
            return

        pos = star_positions[idx]
        for d in '0123456789':
            chars[pos] = d
            if pos < 2:
                if any_prefix_still_possible():
                    dfs(idx + 1)
            else:
                dfs(idx + 1)
        chars[pos] = '*'

    dfs(0)

    result = []
    for name in sorted(counts):
        if counts[name] > 0:
            result.append(f'{name},{counts[name]}')
    return result

Time complexity: O(10^k * n), where k is the number of '*' characters (k <= 5) and n is the card length.. Space complexity: O(k) auxiliary space for recursion, excluding the output list..

Hints

1. Filter by length and prefix compatibility first; unsupported prefixes can be rejected before exploring every completion.
2. If only the final check digit is unknown, every fixed prefix/body determines exactly one valid check digit.

Constraints

• Treat the input as a string.
• The input must end with '?'; otherwise there are no reconstructions.
• Only VISA, MASTERCARD, and AMEX are supported, using the same length/prefix rules as earlier parts.
• Avoid duplicate reconstructions: the same original card may be reachable by more than one error explanation.

Examples

Solution

def solution(card):
    def luhn(num):
        total = 0
        double = False
        for ch in reversed(num):
            d = ord(ch) - 48
            if double:
                d *= 2
                if d > 9:
                    d -= 9
            total += d
            double = not double
        return total % 10 == 0

    def classify(num):
        if len(num) == 16 and num.startswith('4'):
            return 'VISA'
        if len(num) == 16 and num[:2].isdigit() and 51 <= int(num[:2]) <= 55:
            return 'MASTERCARD'
        if len(num) == 15 and num[:2] in ('34', '37'):
            return 'AMEX'
        return None

    if not isinstance(card, str) or not card.endswith('?'):
        return []

    observed = card[:-1]
    if len(observed) not in (15, 16) or not observed.isdigit():
        return []

    results = set()

    def add_candidate(num):
        network = classify(num)
        if network is not None and num != observed and luhn(num):
            results.add((num, network))

    for i, ch in enumerate(observed):
        for d in '0123456789':
            if d == ch:
                continue
            candidate = observed[:i] + d + observed[i + 1:]
            add_candidate(candidate)

    for i in range(len(observed) - 1):
        if observed[i] == observed[i + 1]:
            continue
        candidate = observed[:i] + observed[i + 1] + observed[i] + observed[i + 2:]
        add_candidate(candidate)

    ordered = sorted(results, key=lambda item: int(item[0]))
    return [f'{num},{network}' for num, network in ordered]

Time complexity: O(n^2), because O(11n) candidates are generated and each candidate construction/validation touches O(n) characters.. Space complexity: O(n) auxiliary space, excluding the output list..

Hints

1. Because there was exactly one error, every candidate original card is either one digit substitution away from the observed number or one adjacent swap away.
2. Use a set to deduplicate candidates before sorting the final answers.