Skip to content

Ten first problems, worked through

~45 min · prerequisite: Sliding window over a list

What you will be able to do

  • Read a short problem, pick the pattern from Part 6 that fits it, and write a function for it.
  • Check a fast solution against a brute-force version on small random inputs.
  • Avoid the most common pitfalls for this size.

The idea

Each problem below is an original task, written in the style of short Codeforces problems and aimed at the 800 to 1200 range. None is copied from a contest. Work through them in order, since later problems reuse earlier ideas. The pitfalls are the mistakes that show up most often at this size. Treat the pattern as a first try, and the brute-force method as the reference that shows whether it is right on small cases you can check by hand.

For every problem, follow the same steps. First, read the input format and the limits, and count the work a simple method would need, as in the complexity lesson. Second, write the simple method, because it is the reference for checking. Third, choose the pattern: counting, a formula, a set or dictionary, a sieve, prefix sums, or a window. Fourth, write the fast method and compare the two on many small random inputs. A mismatch means one of them is wrong, and the small input usually shows which one, so keep the small case that fails. A fast idea that looks right can still fail on one small case.

Limits decide which method is allowed. With n up to 2 * 10**5, an n² method needs 4 * 10**10 steps, while an n log2(n) method needs about 3.6 * 10**6. With n in the thousands, n² can be acceptable. Read the limits first.

A judge compares your output with the expected output, so return exactly what the statement asks for.

Worked example

Problem 2 asks: given 0 <= a <= b and k >= 1, how many multiples of k lie in the range from a to b, inclusive?

The multiples of k that are at most x, for x >= 0, are k, 2k, ..., mk, where m = x // k. So there are b // k multiples up to b. Remove those up to a - 1, which gives b // k - (a - 1) // k. When a = 0, the term (a - 1) // k is -1 // k, which is -1, so the formula adds one for the multiple 0 itself.

def count_multiples(a, b, k):
    return b // k - (a - 1) // k


assert count_multiples(3, 10, 3) == 3
assert count_multiples(0, 10, 5) == 3

The ten problems

1. Digit sum (800). Given an integer n that may be negative, return the sum of its decimal digits. The approach is to work on abs(n) and repeatedly take % 10 and // 10. Pitfall: str(n) for a negative number starts with -, which cannot be converted to an integer.

Solution 
def digit_sum(n):
    total = 0
    n = abs(n)
    while n > 0:
        total += n % 10
        n //= 10
    return total


assert digit_sum(2024) == 8
assert digit_sum(-95) == 14
assert digit_sum(0) == 0

2. Multiples in a range (800). Given 0 <= a <= b and k >= 1, count the multiples of k from a to b. The approach is the formula from the worked example. Pitfall: looping from a to b is correct but costs about b - a steps, which can be too many.

Solution 
def count_multiples(a, b, k):
    return b // k - (a - 1) // k


assert count_multiples(3, 10, 3) == 3

3. Above average (800). Given a list of integers, count the values strictly greater than the mean. The approach is to compare x * n with the sum, which keeps everything in integers. Pitfall: dividing to get a float mean can give rounding errors at the boundary.

Solution 
def count_above_average(values):
    total = sum(values)
    n = len(values)
    return sum(1 for x in values if x * n > total)


assert count_above_average([1, 2, 3, 4]) == 2
assert count_above_average([]) == 0

4. Non-decreasing (800). Return True when every value is at least the value before it. The approach is to compare each neighbouring pair. Pitfall: indexing values[i + 1] for every i in range(len(values)) reads past the end.

Solution 
def is_nondecreasing(values):
    return all(a <= b for a, b in zip(values, values[1:]))


assert is_nondecreasing([1, 2, 2, 5]) is True
assert is_nondecreasing([3, 2]) is False
assert is_nondecreasing([]) is True

5. Most frequent letter (900). Given a non-empty string of lowercase letters, return the letter that appears most often. On a tie, return the alphabetically smaller letter. The approach is a Counter and a min with a key of (-count, letter). Pitfall: max(counts, key=counts.get) returns the tied letter that appeared first in the string, which can be the wrong one.

Solution 
from collections import Counter


def most_frequent_letter(s):
    counts = Counter(s)
    return min(counts, key=lambda c: (-counts[c], c))


assert most_frequent_letter("bbaa") == "a"
assert most_frequent_letter("hello") == "l"

6. Highest point (800). Start at height 0. Each U raises the height by one and each D lowers it. Return the highest height reached, counting the start. Pitfall: starting the best value at the first height misses the start, so "DDU" must give 0.

Solution 
def max_height(moves):
    height = 0
    best = 0
    for m in moves:
        height += 1 if m == "U" else -1
        best = max(best, height)
    return best


assert max_height("UUDUD") == 2
assert max_height("DDU") == 0

7. First occurrences (900). Given a list, keep the first occurrence of each value, in the original order. The approach is a set of values already seen, with a list for the answer. Pitfall: list(set(values)) loses the original order, and a set does not promise any order.

Solution 
def unique_in_order(values):
    seen = set()
    out = []
    for x in values:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out


assert unique_in_order([3, 1, 3, 2, 1]) == [3, 1, 2]

8. Equal pairs (1000). Count pairs of positions i < j whose values are equal. The approach is to count each value c times and add c * (c - 1) // 2 pairs for it. Pitfall: c * c counts ordered pairs and includes the pairs of a position with itself.

Solution 
from collections import Counter


def equal_pairs(values):
    return sum(c * (c - 1) // 2 for c in Counter(values).values())


assert equal_pairs([1, 2, 1, 3, 1]) == 3
assert equal_pairs([7, 7, 7, 7]) == 6

9. Primes up to n (1000). For n up to 10**6, count the primes that are at most n. The approach is the sieve from the number theory lesson. Pitfall: 0 and 1 are not prime, so mark them before counting.

Solution 
import math


def count_primes(n):
    if n < 2:
        return 0
    flags = bytearray([1]) * (n + 1)
    flags[0] = 0
    flags[1] = 0
    for p in range(2, math.isqrt(n) + 1):
        if flags[p]:
            flags[p * p::p] = bytes(len(range(p * p, n + 1, p)))
    return sum(flags)


assert count_primes(10) == 4
assert count_primes(100) == 25
assert count_primes(1) == 0

10. Best block (1000). Given a list and k with 1 <= k <= len(values), return the largest sum of k neighbouring values. The approach is a fixed-size window: subtract the value that leaves and add the value that enters. Pitfall: recomputing each block sum costs (n - k + 1) * k steps, which is about n² / 4 when k is half of n.

Solution 
def best_window_sum(values, k):
    total = sum(values[:k])
    best = total
    for i in range(k, len(values)):
        total += values[i] - values[i - k]
        best = max(best, total)
    return best


assert best_window_sum([1, 3, -1, 4, 2], 2) == 6
assert best_window_sum([1, 3, -1, 4, 2], 5) == 9

Try it

The first block checks the formula from problem 2 against a direct count. The second checks problem 8's pair formula against a double loop.

def count_multiples(a, b, k):
    return b // k - (a - 1) // k


for a in range(0, 25):
    for b in range(a, 25):
        for k in range(1, 8):
            brute = sum(1 for x in range(a, b + 1) if x % k == 0)
            assert count_multiples(a, b, k) == brute

from collections import Counter


def equal_pairs(values):
    return sum(c * (c - 1) // 2 for c in Counter(values).values())


for values in ([1, 2, 1, 3, 1], [7, 7, 7, 7], [], [4, 5, 6]):
    brute = sum(1 for i in range(len(values)) for j in range(i + 1, len(values))
                if values[i] == values[j])
    assert equal_pairs(values) == brute

Common mistakes

  1. Converting a negative number's text to digits. The check below fails because the - is not a digit:

    total = sum(int(c) for c in str(-95))

    ValueError: invalid literal for int() with base 10: '-'

    Take abs(n) first.

  2. Reading past the end of a list. Looping over range(len(values)) and reading values[i + 1] fails on the last index:

    values = [1, 2, 2, 5]
ok = all(values[i] <= values[i + 1] for i in range(len(values)))

    IndexError: list index out of range

    Use zip(values, values[1:]) instead.

  3. Choosing a tie-break by accident. max(counts, key=counts.get) keeps the first maximum it finds. For "bbaa" it returns "b", although "a" is the alphabetically smaller tie. Use the explicit key from problem 5 and test a tie.

Practice

  1. Easy: change problem 1 so it returns the number of digits of n. Check digit_count(-95) is 2.
  2. Easy: change problem 3 so it counts values strictly less than the mean. Check the result for [1, 2, 3, 4] is 2.
  3. Medium: change problem 5 so ties go to the letter that appears first in the string. Check most_first_letter("abba") is "a".
  4. Medium: write count_odd_pairs(values) that counts pairs i < j whose sum is odd, using two counters of odd and even values. Check [1, 2, 3, 4] gives 4.
  5. Stretch: write best_at_most(values, k) that returns the largest sum of between 1 and k neighbouring values. Check it on [1, 3, -1, 4, 2] with k = 2, which is 6.
Solution
  1. ```python def digit_count(n): return len(str(abs(n)))

assert digit_count(-95) == 2 ```

  1. ```python def count_below_average(values): total = sum(values) n = len(values) return sum(1 for x in values if x * n < total)

assert count_below_average([1, 2, 3, 4]) == 2 ```

  1. ```python from collections import Counter

def most_first_letter(s): counts = Counter(s) return max(counts, key=counts.get)

assert most_first_letter("abba") == "a" ```

A Counter keeps first-seen order, and max returns the first maximum.

  1. ```python def count_odd_pairs(values): odd = sum(1 for x in values if x % 2 == 1) even = len(values) - odd return odd * even

assert count_odd_pairs([1, 2, 3, 4]) == 4 ```

An odd sum needs one odd and one even value.

  1. ```python def best_at_most(values, k): best = None for size in range(1, k + 1): total = sum(values[:size]) best = total if best is None else max(best, total) for i in range(size, len(values)): total += values[i] - values[i - size] best = max(best, total) return best

assert best_at_most([1, 3, -1, 4, 2], 2) == 6 ```

Recap

  • Start each problem with the limits and a brute-force method, then pick the pattern.
  • Most pitfalls come from the boundaries: negative numbers, the first and last index, ties, and the start of a running best.
  • Compare fast and simple methods on small random inputs.

Sources