Problem Solving with Functions

Real-world analogy

What is it?

Problem solving with functions means breaking complex problems into smaller, manageable pieces. Each piece becomes a function that does one specific task. By combining these small functions, you can solve problems that would be overwhelming to tackle all at once.

Real-world relevance

Real software is built exactly this way! A banking app has functions like calculateInterest(), validatePassword(), transferFunds() — each does one job. Game developers have functions like checkCollision(), updateScore(), renderFrame(). Breaking problems into functions is how all professional software is built.

Key points

• Breaking Problems Down — The #1 skill in CP (and all of programming) is breaking a big problem into smaller parts. If a problem says 'find all prime numbers up to n,' that is really two sub-problems: (1) check if a single number is prime, (2) loop through all numbers and use that check. Make a function for sub-problem 1, then use it in a loop!
• The isPrime Function — One of the most useful functions in CP: bool isPrime(int n). If n < 2, return false. Then check if any number from 2 to sqrt(n) divides n evenly. If yes, it is not prime. If nothing divides it, it is prime. This function runs in O(sqrt(n)) time and is used in countless CP problems.
• GCD — Greatest Common Divisor — GCD is the largest number that divides both a and b. The Euclidean algorithm finds it: gcd(a, b) = gcd(b, a%b), base case gcd(a, 0) = a. C++ has a built-in __gcd(a, b) function (and gcd() in C++17). GCD comes up in fraction problems, LCM calculation (lcm = a*b/gcd), and number theory.
• Pass by Value vs Pass by Reference — By default, C++ copies the argument into the parameter (pass by value). Changes inside the function don't affect the original variable. To modify the original, use pass by reference with &: void swap(int &a, int &b). The & means 'use the original variable, not a copy.' This is essential for functions that need to change their inputs.
• Passing Arrays to Functions — Arrays are always passed by reference in C++ — the function works with the original array, not a copy. Syntax: void sortArray(int arr[], int n). You must also pass the size since the function doesn't know it. This means any changes the function makes to the array affect the original!
• Recursive Functions (Preview) — A recursive function is one that calls itself! For example, factorial: int fact(int n) { if (n <= 1) return 1; return n * fact(n-1); }. It keeps calling itself with smaller inputs until it hits the base case. Recursion is powerful but be careful — without a base case, it runs forever!
• Function Design Tips for CP — Tips for writing good CP functions: (1) Each function should do ONE thing. (2) Give functions clear names like isPrime, findMax, countVowels. (3) Keep functions short — 5 to 15 lines is ideal. (4) Test each function independently before using it in your solution. (5) Common CP functions to have ready: isPrime, gcd, power, isPalindrome.
• Building a Function Library — Experienced CP contestants have a personal library of tested functions they can paste into any solution: isPrime, gcd, lcm, power with mod, binary search, etc. As you solve more problems, you will build your own library. This is like having a toolbox — the more tools you have, the faster you can solve problems!

Code example

#include <bits/stdc++.h>
using namespace std;

// Check if a number is prime
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// GCD using Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// LCM using GCD
int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // Divide first to avoid overflow!
}

// Swap using pass by reference
void mySwap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

// Count primes in an array — combining functions!
int countPrimes(int arr[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (isPrime(arr[i])) {
            count++;
        }
    }
    return count;
}

int main() {
    // Using isPrime
    for (int i = 1; i <= 20; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }
    cout << endl;  // Output: 2 3 5 7 11 13 17 19
    
    // Using gcd and lcm
    cout << "GCD(12, 8) = " << gcd(12, 8) << endl;   // 4
    cout << "LCM(12, 8) = " << lcm(12, 8) << endl;   // 24
    
    // Using pass by reference
    int x = 10, y = 20;
    mySwap(x, y);
    cout << "After swap: x=" << x << " y=" << y << endl;  // x=20 y=10
    
    // Using countPrimes
    int arr[] = {4, 7, 10, 13, 15, 17, 20, 23};
    cout << "Primes in array: " << countPrimes(arr, 8) << endl;  // 4
    
    return 0;
}

Line-by-line walkthrough

1. 1. isPrime checks if n < 2 first (0 and 1 are not prime). Then it checks divisors from 2 to sqrt(n) using i*i <= n.
2. 2. If any divisor divides n evenly (n % i == 0), we immediately return false — it is not prime.
3. 3. If no divisor works, we return true — the number is prime!
4. 4. gcd uses the Euclidean algorithm: keep replacing (a, b) with (b, a%b) until b becomes 0. Then a is the GCD.
5. 5. lcm divides first (a / gcd) then multiplies by b to avoid overflow.
6. 6. mySwap uses & (pass by reference) so changing a and b inside the function changes x and y in main.
7. 7. countPrimes combines the array loop pattern with our isPrime function — this is the power of functions!
8. 8. In main, we use all our functions together to solve different problems with clean, readable code.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    cout << isPrime(1) << endl;  // Should print 0 (false)
    cout << isPrime(2) << endl;  // Should print 1 (true)
    cout << isPrime(7) << endl;  // Should print 1 (true)
    cout << isPrime(1000000007) << endl;  // Should print 1, but takes forever!
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Problem Decomposition for CP (Errichto)
• Number Theory Basics for CP (CP-Algorithms)
• Number Theory Problems (Codeforces)