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
Sum
Formula
Example
1 + 2 + … + n
n(n + 1) / 2
n = 100 → 5050
1² + 2² + … + n²
n(n + 1)(2n + 1) / 6
n = 3 → 14
1³ + 2³ + … + n³
(n(n + 1) / 2)²
n = 3 → 36
a + (a+d) + … (n terms)
n · (2a + (n − 1)d) / 2
an arithmetic sequence
1 + q + q² + … + qn−1
(qⁿ − 1) / (q − 1)
q = 2: 2ⁿ − 1
a + (a+1) + … + b
(a + b)(b − a + 1) / 2
3 + … + 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
Question
Formula
Why
how many handshakes there are among n people (everyone with everyone)
n(n − 1) / 2
pairs without order
how many ordered pairs of different elements
n(n − 1)
the first, then the second
how many subarrays (contiguous parts) an array of length n has
n(n + 1) / 2
the start and the end are chosen
how many squares (of all sizes) an n × n board has
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
Hint
There are (n − k + 1)² squares with the side k, so in total 1² + 2² + … + n² = n(n + 1)(2n + 1)/6. For n = 106 the product is about 2·1018 – it still fits in a long long (up to 9.2·1018).
Solution (C++)
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
cout << n * (n + 1) * (2 * n + 1) / 6 << endl; // 1² + 2² + ... + n²
return 0;
}
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
Hint
From 1 to b there are b / k divisible numbers, and from 1 to a − 1 there are (a − 1) / k; the answer is the difference.
Solution (C++)
#include <iostream>
using namespace std;
int main() {
long long a, b, k;
cin >> a >> b >> k;
cout << b / k - (a - 1) / k << endl;
return 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
Hint
There are n(n − 1) ordered pairs of different teams.
Solution (C++)
#include <iostream>
using namespace std;
int main() {
long long n;
cin >> n;
cout << n * (n - 1) << endl;
return 0;
}
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?
Podešavanja kolačića
Koristimo kolačiće da bismo vam pružili najbolje moguće iskustvo. Takođe nam omogućavaju da analiziramo ponašanje korisnika kako bismo stalno poboljšavali veb lokaciju za vas.