Constraints

• 0 <= len(nums) <= 10^5
• -10^18 <= nums[i], start <= 10^18
• nums contains only integers
• If 0 appears in nums, the original function would not terminate

Examples

Solution

def solution(nums, start):
    issues = [
        'default_mutable_cache',
        'input_list_mutation_during_iteration',
        'keying_by_stringified_mutable_list',
        'potential_nontermination_when_zero_present',
        'quadratic_time_from_repeated_stringify',
        'unbounded_cache_growth_across_calls',
    ]

    arr = list(nums)
    if 0 in arr:
        return (False, None, None, issues)

    total = start
    i = 0
    while i < len(arr):
        n = arr[i]
        if n % 2 == 0:
            arr.append(n // 2)
        total += n
        i += 1

    return (True, total, arr, issues)

Time complexity: O(n + s), where s is the number of appended half-values before termination. Space complexity: O(n + s).

Hints

1. In Python, a for-loop over a list can visit items appended before the loop ends.
2. Among integers, repeatedly applying n // 2 to an even number only loops forever for 0.

Constraints

• 0 <= len(nums) <= 10^5 for valid cases
• -10^18 <= nums[i], start <= 10^18 for valid cases
• bool values are considered invalid even though bool is a subclass of int in Python

Examples

Solution

def solution(nums, start=0, use_cache=False):
    """
    Return start plus the sum of each integer's even-halving chain.

    Preconditions:
    - nums must be a list of plain ints, or None for invalid input.
    - start must be a plain int.
    - use_cache must be a bool.

    Postconditions:
    - nums is not mutated.
    - Returns an int for valid input, otherwise None.
    - Always terminates; 0 contributes 0 exactly once.
    """
    if nums is None or not isinstance(nums, list):
        return None
    if type(start) is not int or type(use_cache) is not bool:
        return None
    for n in nums:
        if type(n) is not int:
            return None

    memo = {} if use_cache else None

    def contribution(n):
        if memo is not None and n in memo:
            return memo[n]

        total = 0
        cur = n
        while True:
            total += cur
            if cur == 0 or cur % 2 != 0:
                break
            cur //= 2

        if memo is not None:
            memo[n] = total
        return total

    total = start
    for n in nums:
        total += contribution(n)
    return total

Time complexity: Without caching: O(n log V). With caching: O(u log V + n), where u is the number of distinct values and V is the maximum absolute value.. Space complexity: O(1) without caching, O(u) with caching.

Hints

1. Process each number independently; you do not need to append into the original list.
2. A repeated number should have the same contribution every time, which makes memoization natural.

Constraints

• 1 <= number of candidates <= 20
• 0 <= number of required tags <= 15
• Candidate names are unique strings

Examples

Solution

def solution(candidates, required_tags):
    required = sorted(set(required_tags))
    if not required:
        return []

    tag_index = {tag: i for i, tag in enumerate(required)}
    processed = []
    for name, tags in candidates:
        mask = 0
        for tag in set(tags):
            if tag in tag_index:
                mask |= 1 << tag_index[tag]
        processed.append((name, mask))

    processed.sort(key=lambda x: x[0])
    full_mask = (1 << len(required)) - 1

    best = {0: ()}

    def better(a, b):
        if b is None:
            return True
        return (len(a), a) < (len(b), b)

    for name, mask in processed:
        snapshot = list(best.items())
        for old_mask, names in snapshot:
            new_mask = old_mask | mask
            new_names = names + (name,)
            prev = best.get(new_mask)
            if better(new_names, prev):
                best[new_mask] = new_names

    if full_mask not in best:
        return None
    return list(best[full_mask])

Time complexity: O(c * 2^r), where c is the number of candidates and r is the number of required tags. Space complexity: O(2^r).

Hints

1. Map each required tag to a bit position, then each test becomes a bitmask.
2. Dynamic programming over covered-tag masks can find the minimum-size subset with deterministic tie-breaking.

Constraints

• 0 <= total dependency entries <= 200
• Versions use numeric dot-separated semantic versioning such as 1.2.3
• Package names are non-empty strings without spaces

Examples

Solution

def solution(project_dir, runtime_deps, dev_deps):
    def parse_version(version):
        return tuple(int(part) for part in version.split('.'))

    merged = {}
    all_deps = list(runtime_deps) + list(dev_deps) + [('pytest', '8.2.2'), ('build', '1.2.1')]

    for name, version in all_deps:
        norm = name.lower()
        if norm not in merged or parse_version(version) > parse_version(merged[norm]):
            merged[norm] = version

    pinned = ' '.join(f"{name}=={merged[name]}" for name in sorted(merged))

    return [
        f"cd {project_dir}",
        'python3 -m venv .venv',
        'source .venv/bin/activate',
        'python -m pip install --upgrade pip',
        f"python -m pip install {pinned}",
        'python -m pip freeze > requirements-lock.txt',
        'pytest -q',
        'python -m build --wheel',
    ]

Time complexity: O(d log d), where d is the number of dependency entries after normalization. Space complexity: O(d).

Hints

1. Normalize package names to lowercase before deduplicating.
2. Compare semantic versions component by component, not as raw strings.

Constraints

• 0 <= len(features) <= 4
• features contains strings
• coverage_threshold is only validated when 'coverage' is enabled

Examples

Solution

def solution(features, coverage_threshold, cli_name, cli_target):
    valid = {'lint', 'mypy', 'coverage', 'cli'}
    feature_set = set(features)

    if not feature_set.issubset(valid):
        return None
    if not feature_set:
        return ([], None)
    if 'coverage' in feature_set:
        if type(coverage_threshold) is not int or not (0 <= coverage_threshold <= 100):
            return None
    if 'cli' in feature_set:
        if not cli_name or not cli_target:
            return None

    deps = {'setup': set()}
    if 'lint' in feature_set:
        deps['lint'] = {'setup'}
    if 'mypy' in feature_set:
        deps['mypy'] = {'setup'}
    if 'coverage' in feature_set:
        deps['test'] = {'setup'}
    if 'cli' in feature_set:
        build_needs = {'setup'}
        for node in ('lint', 'mypy', 'test'):
            if node in deps:
                build_needs.add(node)
        deps['build'] = build_needs

    order = []
    done = set()
    while len(done) < len(deps):
        ready = sorted(node for node, need in deps.items() if node not in done and need <= done)
        if not ready:
            return None
        node = ready[0]
        done.add(node)
        order.append(node)

    commands = []
    for node in order:
        if node == 'setup':
            commands.append('python -m pip install -e .[dev]')
        elif node == 'lint':
            commands.append('ruff check .')
        elif node == 'mypy':
            commands.append('mypy src')
        elif node == 'test':
            commands.append(f'pytest --cov=src --cov-fail-under={coverage_threshold}')
        elif node == 'build':
            commands.append('python -m build')

    entry_point = f'{cli_name}={cli_target}' if 'cli' in feature_set else None
    return (commands, entry_point)

Time complexity: O(v^2 log v), where v is the number of workflow nodes. Space complexity: O(v + e).

Hints

1. Treat each CI action as a graph node and use topological sorting.
2. A deterministic tie-break rule is needed whenever several jobs become available together.