Divide and Conquer

Lesson 6 of 7 · Advanced techniques

A big problem is divided into smaller problems of the same kind, they are solved (usually recursively), and then their solutions are combined. Binary search, merge sort, quick sort and fast exponentiation are all based on this idea.

Before you start: prerequisites – recursion, merge sort.
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++.

Three steps

StepWhat it doesMerge sortBinary search
Dividethe problem into smaller partsthe array into two halvesthe interval into two halves
Conquereach part (recursively)sort both halvescontinue in only one
Combinethe solutions of the partsmerging sorted arrays, O(n)nothing

The complexity depends on the number of parts, their size and the cost of combining:

RecurrenceComplexityExample
T(n) = T(n/2) + O(1)O(log n)binary search, fast exponentiation
T(n) = 2T(n/2) + O(n)O(n log n)merge sort, the number of inversions
T(n) = 2T(n/2) + O(1)O(n)the maximum of an array, recursively
T(n) = T(n − 1) + O(n)O(n²)a badly divided problem (quick sort in the worst case)

The gain comes from dividing the problem into equal parts: then there are only log₂ n levels of recursion.

Example: fast exponentiation

aⁿ = (an/2)² for an even n and a · an−1 for an odd n. Every step halves the exponent – O(log n) multiplications instead of n.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long power(long long a, long long n) {
    if (n == 0) return 1;                     // a^0 = 1
    long long p = power(a, n / 2);            // solve the problem of half the size (once!)
    p = p * p % MOD;                          // combine
    if (n % 2 == 1) p = p * a % MOD;          // an odd exponent
    return p;
}

int main() {
    long long a, n;
    cin >> a >> n;
    cout << power(a % MOD, n) << endl;
    return 0;
}

It is important to call power(a, n / 2) once and store the result; two calls would bring the complexity back to O(n). More details in the lesson Fast exponentiation algorithm.

Example: the largest sum of a contiguous part

The best part of the array is either entirely in the left half, or entirely in the right half, or it crosses the middle. The recursion solves the first two cases, and the third one – the best suffix of the left half plus the best prefix of the right half – is computed in O(n). In total O(n log n).

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

vector<long long> a;

long long bestSum(int lo, int hi) {
    if (lo == hi) return a[lo];                      // one element
    int mid = (lo + hi) / 2;
    long long left = bestSum(lo, mid), right = bestSum(mid + 1, hi);
    // the part that crosses the middle: the best suffix on the left + the best prefix on the right
    long long s = 0, bestLeft = LLONG_MIN;
    for (int i = mid; i >= lo; i--) { s += a[i]; bestLeft = max(bestLeft, s); }
    s = 0;
    long long bestRight = LLONG_MIN;
    for (int i = mid + 1; i <= hi; i++) { s += a[i]; bestRight = max(bestRight, s); }
    return max({left, right, bestLeft + bestRight});
}

int main() {
    int n;
    cin >> n;
    a.resize(n);
    for (auto &x : a) cin >> x;
    cout << bestSum(0, n - 1) << endl;
    return 0;
}

There is also an O(n) solution of this problem – Kadane's algorithm, but the divide and conquer version shows the general pattern: whatever crosses the border between the parts is computed while combining.

Where else it is used

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: easy

The maximum by divide and conquer

Write a recursive function that finds the largest element of an array by dividing it into two halves.

Example

Input

6
3 9 -1 7 9 2

Output

9
TASK 02Difficulty: easy

How many times does x appear?

A sorted array and a number x are given. Print how many times x appears, in O(log n).

Example 1

Input

8
1 2 2 2 3 5 5 8
2

Output

3

Example 2

Input

3
1 2 3
4

Output

0
Common mistakes and tips
  • The parts should be roughly equal – otherwise the logarithmic depth is lost.
  • Compute the result of a subproblem that is used twice only once and store it.
  • Watch out for the base case (an interval of one element) so that the recursion is not infinite.

Check your knowledge

Open the quiz

Divide and conquer

1. What are the steps of the divide and conquer technique?




2. What is the complexity if T(n) = 2T(n/2) + O(n)?




3. Why is it important to call power(a, n/2) only once in fast exponentiation?