Improving the Complexity of an Algorithm – Examples

Page 2 of 5 · Algorithm examples

This page offers example tasks for improving the complexity of algorithms. It includes different problems such as optimizing water polo training, counting particular substrings, finding a missing number and computing the sums of rows in an arithmetic triangle. Every example is a challenge in analysing the complexity and efficiency of a solution.

Before you start: read the lesson Replacing iteration with a formula (SR).
How to practise: first try to solve the task on your own (at least on paper), then open the hint, and the solution only at the end. The solutions are most often in C or C++; if you are learning Java or Python, rewrite the idea in your language.
TASK 01

The n-th day of training

On the planet of superheroes, water polo players take part in a training camp for a competition that lasts n days. On the first day of the camp a water polo player swims a metres, and on every following day d metres more than on the previous day. Write a program that finds, for every water polo player in the club, how many metres they swim on the last day of the camp.

Input: The first line of the standard input contains the number of days of the camp n (n ≤ 105). Every following line of the standard
input contains the data for one water polo player (at most 105 of them). Two numbers separated by a
space are entered: the number of metres the player swims on the first day of the camp a (a ≤ 3000), and the number of metres they
swim more every day than on the previous day d (d ≤ 1000).

Output:

On the standard output, for every water polo player, print how many metres they swim on the last day of the camp.

Example:

Input:
10
500 100
400 20

Output:

1400
580
Read the explanation of the task on the page: Replacing iteration with a formula (SR)

TASK 02

The number of substrings that start and end with 1

We are given a binary string (a string of characters that consists of the characters 0 and 1). Write a program that finds the number of segments (substrings of consecutive elements) of length at least 2 that start and end with 1.

Input:

The first and only line of the standard input contains a binary string (made of 0 and 1).

Output:

On the standard output print the required number of segments in one line.

Example:

Input:
010001001

Output:

3
Read the explanation of the task on the page: Replacing iteration with a formula (SR)

TASK 03

The missing number

In the sequence of numbers from 0 to n exactly one number is missing. Write a program that, without storing the elements of the sequence, reads the numbers from the input and efficiently finds which number is missing.

Input:

The number n (1 ≤ n ≤ 109) is read from the standard input, and then the described sequence of numbers (the numbers are given in one line, separated by single spaces).

Output:

Print the missing element on the standard output.

Example:

Input:
5
0 4 2 5 1

Output:

3

TASK 04

An arithmetic triangle

What is the sum of the numbers in a given row of the following triangle:

         1
      2  3  4
   5  6  7  8  9
10 11 12 13 14 15 16
        ...

Input:

The number k (1 ≤ k ≤ 5 · 105) of the row of the triangle whose sum should be computed (row numbering starts from 1)

Output:

The sum of the values in the given row of the triangle.

Example:

Input:
3

Output:

35