Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 63 ยท Practice and Review

Practice: Warm-Up Problems with Solutions

Twelve easy contest problems with ideas, runnable Python solutions, tests and complexity notes. A gentle start for building speed and confidence.

Reading about techniques is not the same as using them under a clock. This lesson gives you twelve easy problems, each with a short statement, the key idea, a complete runnable solution and a complexity note. They are deliberately small: most can be solved in five to fifteen minutes once you know the trick. Think of them as scales for a pianist. You are not here to learn new theory, but to make the basics fast and automatic.

Use the lesson actively. For every problem, read the statement and stop. Try to name an algorithm and its complexity before you read the idea. Then run the code, change the inputs and break it. The habit of estimating cost first comes from estimating time and memory, and the habit of testing against a slow version comes from stress testing.

flowchart TD
  A["Read the statement"] --> B["Check constraints<br/>and estimate the budget"]
  B --> C["Pick an idea<br/>and say its complexity"]
  C --> D["Code a function<br/>of the parsed input"]
  D --> E["Run samples<br/>and tiny edge cases"]
  E --> F{"Passes?"}
  F -- "no" --> G["Find the bug by hand<br/>or with a brute force"]
  G --> D
  F -- "yes" --> H["Submit"]

The routine to practice on every problem, even easy ones.

All solutions below are functions that take parsed data and return a value. That keeps them testable, as recommended in templates and habits.

Problems 1 to 4: counting and scanning

Problem 1: Lucky numbers. Given n (at most 100,000), count the integers from 1 to n whose digit sum is divisible by 7. Idea: the limit is small, so check every number: convert to a string, add the digits. Cost O(n log n) in the number of digits. For n = 30 the lucky numbers are 7, 16 and 25, so the answer is 3.

Problem 2: Largest gap. Given a list of integers (at least two), find the largest difference between two neighbors after sorting. Idea: sort, then compare adjacent elements. Cost O(n log n). For [5, 1, 9, 3] the sorted list is 1 3 5 9, and the gaps are 2, 2 and 4.

Problem 3: Bracket repair. A string of ( and ) is given. What is the smallest number of characters you must insert to make it a correctly balanced sequence? Idea: scan from left to right and keep the number of currently unmatched (. When you see ) and nothing is open, you must insert one (. At the end, every unmatched ( needs a ). Cost O(n). Only one kind of bracket is used, so a counter is enough and no stack is needed.

Problem 4: Pairs with a given sum. Count the pairs i < j with a[i] + a[j] = k. Idea: walk through the array and keep a counter of values seen so far. For each x, every earlier k - x forms a pair with it. Cost O(n). Duplicates are handled automatically because the counter holds multiplicities.

Python Problems 1 to 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the sample for problem 4 the answer is 4: the pair (1, 5) plus the three pairs among the three 3s. If you had used a set, you would have lost the duplicates, a classic mistake.

Problems 5 to 8: arrays and strings

Problem 5: The missing number. An array holds n - 1 distinct integers from 1..n. Which one is missing? Idea: the sum of 1..n is n(n+1)/2; subtract the array sum. Cost O(n) time and O(1) space. Python integers never overflow, but in other languages the sum can, which is why an XOR of all values is the safe alternative (see bit tricks and XOR problems).

Problem 6: Longest run. Find the length of the longest block of equal consecutive characters in a string. Idea: one pass with a current run length that resets to 1 when the character changes. Cost O(n). Remember the one-character string: the answer is 1, not 0.

Problem 7: Rotate. Rotate an array left by k positions, where k may be larger than the length. Idea: reduce k modulo the length, then slice: a[k:] + a[:k]. Cost O(n). Do not forget the empty array, where the modulo would divide by zero.

Problem 8: Pairs with a given difference. Count the pairs i < j with |a[i] - a[j]| = d, where d >= 0. Idea: count values with a Counter. For d > 0, each value x pairs with every copy of x + d, contributing cnt[x] * cnt[x + d]. For d = 0 the pairs are inside one group: c(c-1)/2. Cost O(n). Splitting off d = 0 is the edge case, because otherwise a value would pair with itself.

Python Problems 5 to 8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When a counting problem has a special case such as d = 0 or k even (a value pairing with itself), test it explicitly. Random tests with a small value range hit those cases within a few runs, which is why the generators above use values in 0..5.

Problems 9 to 12: math, DP and sweeps

Problem 9: Anagrams. Are two strings anagrams, meaning one is a rearrangement of the other? Idea: compare letter counts. Cost O(n). Sorting both strings also works in O(n log n), but counting is shorter and faster.

Problem 10: Trailing zeros of a factorial. How many zeros end n!, for n up to 10^18? Idea: a trailing zero comes from a factor 10 = 2 x 5, and factors of 2 are plentiful, so count factors of 5. There are n // 5 multiples of 5, plus n // 25 that contribute a second 5, and so on. Cost O(log n). You never compute n! itself, since for n = 10^18 it would have more digits than any computer can store; the formula is the whole solution. See the number theory toolkit for related counting arguments.

Problem 11: Staircase. You climb n steps, taking 1 or 2 steps at a time. How many different sequences reach the top? Print it modulo 1,000,000,007, with n up to 100,000. Idea: the last move was a 1-step or a 2-step, so ways(n) = ways(n-1) + ways(n-2). This is the Fibonacci recurrence. Cost O(n), keeping only two values and reducing modulo each time, as in modular arithmetic.

Problem 12: Busiest moment. You get n half-open intervals [start, end). What is the largest number that overlap at the same time? Idea: a sweep over events. Create (start, +1) and (end, -1) events, sort them, and keep a running sum. Sorting tuples puts -1 before +1 at equal times, so an interval ending at time 4 does not count as overlapping one that starts at 4. Cost O(n log n). This is the pattern from sorting, events and sweeps.

Python Problems 9 to 12

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows why reading the statement matters. With half-open intervals the answer is 2, but if the end time is included, three intervals touch at time 4 and the answer is 3. Neither is wrong; they answer different questions, and only the statement says which one you need.

How to use these problems

  • Time yourself. Aim for under ten minutes per problem, including testing. If a warm-up takes thirty, that tells you which technique to review.
  • Re-solve without looking. The next day, solve three of them from a blank file. Reading a solution feels like understanding but is not the same as producing it.
  • Change the constraints. What if n in problem 1 were 10^9? (The brute force dies, and you would need digit DP, covered in bitmask and digit DP.) What if the list in problem 4 were sorted? (Two pointers with no extra memory.) Changing one number often turns an easy problem into a lesson.
  • Write the brute force first for at least two problems. It is a good way to see how little code correctness needs.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does the pair-counting solution use a Counter of values seen so far instead of a set?

    With values [1, 5, 3, 3, 3] and k = 6 there are three pairs among the 3s. A set would see only one 3 and lose them.
  2. 2. How many trailing zeros does 100! have, and why can the answer be found without computing 100!?

    Each trailing zero needs a factor 5 and a factor 2, and 2s are plentiful. 100//5 + 100//25 = 20 + 4 = 24.
  3. 3. In the interval sweep, why must an end event sort before a start event at the same time for half-open intervals?

    Interval [1, 4) ends exactly when [4, 5) starts. Processing the -1 first removes it before the new one is added, so they are never both counted.
  4. 4. What is the time complexity of the staircase solution for n = 100,000, and why take the modulus inside the loop?

    The loop runs n times with two variables. Reducing at every step avoids huge integers and gives the answer modulo the requested prime.

Summary

  • Warm-up problems train speed on the basics: counting with a Counter, sorting, one-pass scans, formulas and small DP.
  • Estimate the complexity before coding and test small edge cases (empty input, one element, d = 0).
  • Counting multiplicities, not just presence, is the most common detail in pair-counting problems.
  • Factorial zeros, Fibonacci-style recurrences and event sweeps are patterns that reappear in much harder problems.
  • Re-solving from a blank file and changing the constraints turns a solved problem into lasting skill.

Next: Practice: Intermediate Problems with Solutions