How to Speed Up a Solution: Typical Optimisations

Lesson 4 of 4 · Algorithm complexity

The first solution that comes to mind is often correct, but too slow. This lesson shows the most common ways to speed up a solution – from fewer steps in a loop, through remembering what has already been calculated, to choosing a better data structure – and when each idea helps.

Before you start: prerequisites – algorithm complexity.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Fewer steps: divisors up to √n

The divisors of a number come in pairs d and n / d, and the smaller of them is at most √n. That is why it is enough to check up to the square root: O(√n) instead of O(n). For n = 1012 that is 106 steps instead of 1012.

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long count = 0;
    for (long long d = 1; d * d <= n; d++) {
        if (n % d == 0) {
            count++;                      // the divisor d
            if (d != n / d) count++;      // and its pair n/d (if it is not the same, for squares)
        }
    }
    cout << count << endl;
    return 0;
}

Do not calculate the same thing twice

If the same value is calculated several times in a loop, calculate it once before the loop. If queries ask for sums of parts of an array – prepare prefix sums. If recursion calculates the same subproblems – remember the results (dynamic programming).

SlowFasterGain
the sum of a part of the array with a loop for every queryprefix sumsO(n·q) → O(n + q)
for (i = 0; i < strlen(s); i++)int len = strlen(s); before the loopO(n²) → O(n)
recursive Fibonaccian array with remembered valuesO(2ⁿ) → O(n)
checking "is it prime" for every number up to nthe sieve of EratosthenesO(n√n) → O(n log log n)

A better data structure

The repeated operationSlowFast
"has x already been seen?"a pass through the array, O(n)set or an array of counters, O(log n) / O(1)
"which one is currently the smallest?"finding the minimum, O(n)priority_queue, O(log n)
"how many elements are ≤ x?"counting, O(n)sorting + upper_bound, O(log n)
erasing from the beginningvector::erase(begin), O(n)deque or queue, O(1)
the sum of a part of the array with updatesa loop, O(n)a Fenwick tree, O(log n)

Fast input and output

With large inputs (106 numbers) even reading alone can take too long. Two lines at the beginning of main speed up cin and cout several times, and "\n" instead of endl does not flush the output after every line:

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);   // cin/cout without synchronising with scanf/printf
    cin.tie(nullptr);              // cin does not wait for cout to be flushed
    int n;
    cin >> n;
    long long s = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s += x;
    }
    cout << s << "\n";             // "\n" instead of endl
    return 0;
}

After these lines do not mix cin with scanf or cout with printf.

The order of thinking

  1. Write the simplest correct solution (brute force) and check it on the examples.
  2. Calculate its complexity and compare it with the constraints (the table).
  3. If it is too slow: what is repeated? Can it be remembered, prepared in advance, counted with a formula, or found with sorting and binary search?
  4. Keep the slower solution – you use it to check the faster one on random small examples.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

Perfect numbers

A number is perfect if it equals the sum of its divisors smaller than itself (6 = 1 + 2 + 3). For a given number n ≤ 1012 print YES if it is perfect, and NO otherwise.

Example 1

Input

6

Output

YES

Example 2

Input

28

Output

YES

Example 3

Input

12

Output

NO

Example 4

Input

137438691328

Output

YES
TASK 02Difficulty: easy

The first repeated number

n ≤ 2·105 numbers up to 109 are given. Print the first number (looking from the left) that has already appeared before, or -1. An O(n²) solution is too slow.

Example 1

Input

6
5 3 9 3 5 1

Output

3

Example 2

Input

3
1 2 3

Output

-1
Common mistakes and tips
  • Optimise only when you have a correct solution – fast but wrong is worthless.
  • In the loop d * d <= n use long long, otherwise d * d overflows.
  • endl in a loop with a million outputs can slow the program down more than the calculation itself.

Check your knowledge

Open the quiz

Speeding up a solution

1. Up to which number is it enough to look for the divisors of the number n?




2. What speeds up repeated queries "the sum from l to r"?




3. What is ios::sync_with_stdio(false) for?