Formulas Instead of Loops: Sums and Counting

Lesson 3 of 4 · Algorithm complexity

Many loops in tasks only add or count. For such loops there is often a ready-made formula that gives the result immediately, even for numbers larger than a billion. This lesson collects the most useful formulas, with programs and checks on examples.

Before you start: prerequisites – replacing iteration with a formula (SR), combinatorics (SR).
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++.

The most important sums

SumFormulaExample
1 + 2 + … + nn(n + 1) / 2n = 100 → 5050
1² + 2² + … + n²n(n + 1)(2n + 1) / 6n = 3 → 14
1³ + 2³ + … + n³(n(n + 1) / 2)²n = 3 → 36
a + (a+d) + … (n terms)n · (2a + (n − 1)d) / 2an arithmetic sequence
1 + q + q² + … + qn−1(qⁿ − 1) / (q − 1)q = 2: 2ⁿ − 1
a + (a+1) + … + b(a + b)(b − a + 1) / 23 + … + 7 = 25
The order of operations: in the formula n * (n + 1) / 2 you first multiply and then divide – the product is always even, so the division is exact. For n up to 109 the product is up to 1018, so you need long long. For n of 2·109 and more – divide the even factor before multiplying.

How many numbers are divisible by k?

From 1 to n there are exactly n / k (integer division) numbers divisible by k. In the interval [a, b] there are b / k − (a − 1) / k of them (for positive a and b). Their sum is k · (1 + 2 + … + m) = k · m(m + 1) / 2, where m = n / k.

For numbers divisible by 3 or 5 inclusion–exclusion is used: divisible by 3 + divisible by 5 − divisible by 15 (they have been counted twice).

#include <iostream>
using namespace std;

// the sum of all the numbers from 1 to n that are divisible by k
long long sumDivisible(long long n, long long k) {
    long long m = n / k;                 // there are this many of them: k, 2k, ..., mk
    return k * (m * (m + 1) / 2);
}

int main() {
    long long n;
    cin >> n;
    // divisible by 3 or 5 = by 3 + by 5 - by 15
    cout << sumDivisible(n, 3) + sumDivisible(n, 5) - sumDivisible(n, 15) << endl;
    return 0;
}

For n = 10: 3 + 5 + 6 + 9 + 10 = 33. A loop up to 109 would take a second, while the formula is instant and works even for 1012 (with care about overflow).

Counting pairs and arrangements

QuestionFormulaWhy
how many handshakes there are among n people (everyone with everyone)n(n − 1) / 2pairs without order
how many ordered pairs of different elementsn(n − 1)the first, then the second
how many subarrays (contiguous parts) an array of length n hasn(n + 1) / 2the start and the end are chosen
how many squares (of all sizes) an n × n board has1² + 2² + … + n²there are (n − k + 1)² squares of size k
how many rectangles an n × m board hasC(n+1, 2) · C(m+1, 2)two horizontal and two vertical lines are chosen
how many subsets a set of n elements has2ⁿevery element is either inside or not

More about this is in the lesson Combinatorics (SR).

Counting by groups

A common idea: instead of counting pairs directly, count the elements by groups and apply a formula to every group. Example: how many pairs of positions i < j are there with a[i] = a[j]? If the value v appears c times, it gives c(c − 1)/2 pairs:

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<long long, long long> count;         // how many times every value appears
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        count[x]++;
    }
    long long pairs = 0;
    for (auto &p : count) pairs += p.second * (p.second - 1) / 2;
    cout << pairs << endl;
    return 0;
}

For the input 6 / 1 2 1 3 2 1 the program prints 4 (the value 1 gives 3 pairs, and the value 2 one pair). Instead of O(n²) comparisons of all the pairs – O(n log n). This is the same idea as in the task with a binary string in the lesson Replacing iteration with a formula (SR).

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

Squares on a board

How many squares of all sizes are there on an n × n board (1 ≤ n ≤ 106)? On a chessboard (n = 8) there are 204.

Example 1

Input

1

Output

1

Example 2

Input

2

Output

5

Example 3

Input

8

Output

204

Example 4

Input

1000000

Output

333333833333500000
TASK 02Difficulty: easy

Divisible numbers in an interval

The numbers a, b and k are given (1 ≤ a ≤ b ≤ 1018, 1 ≤ k ≤ 1018). How many numbers from [a, b] are divisible by k?

Example 1

Input

1 10 3

Output

3

Example 2

Input

10 20 5

Output

3

Example 3

Input

7 7 2

Output

0
TASK 03Difficulty: easy

Matches in a tournament

n teams (n ≤ 109) play in a tournament, and every team plays every other team twice (at home and away). How many matches are there?

Example 1

Input

4

Output

12

Example 2

Input

1000000000

Output

999999999000000000
Common mistakes and tips
  • Before dividing check that the product is divisible (n(n + 1) is always even).
  • For n up to 109 and more use long long in all the intermediate results.
  • Check the formula on a small example (n = 1, 2, 3) – and compare it with a loop.

Check your knowledge

Open the quiz

Formulas instead of loops

1. What is 1 + 2 + … + 200?




2. How many numbers from 1 to 100 are divisible by 7?




3. How many contiguous parts does an array of 5 elements have?