C++ Top Codes

C++ Fibonacci Series Program: Loop, Recursion and Memoization

The Fibonacci series starts with 0, 1 and every next number is the sum of the two numbers before it: 0, 1, 1, 2, 3, 5, 8, 13...

1. Using a loop (the best way)

#include <iostream>

int main() {
    int count = 12;
    unsigned long long a = 0, b = 1;
    for (int i = 0; i < count; i++) {
        std::cout << a << ' ';
        unsigned long long next = a + b;
        a = b;
        b = next;
    }
    std::cout << '\n';
}

2. Using recursion

#include <iostream>

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    for (int i = 0; i < 12; i++) std::cout << fib(i) << ' ';
    std::cout << '\n';
}

Simple, but it repeats the same work again and again, so it is very slow for numbers like fib(45).

3. Recursion with memoization

#include <iostream>
#include <unordered_map>

unsigned long long fib(int n, std::unordered_map<int, unsigned long long>& cache) {
    if (n <= 1) return n;
    if (auto it = cache.find(n); it != cache.end()) return it->second;
    return cache[n] = fib(n - 1, cache) + fib(n - 2, cache);
}

int main() {
    std::unordered_map<int, unsigned long long> cache;
    std::cout << fib(10, cache) << '\n';
    std::cout << fib(50, cache) << '\n';
    std::cout << fib(90, cache) << '\n';
}

4. At compile time with constexpr

#include <array>
#include <iostream>

constexpr unsigned long long fib(int n) {
    unsigned long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        unsigned long long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

int main() {
    constexpr auto table = [] {
        std::array<unsigned long long, 10> t{};
        for (int i = 0; i < 10; i++) t[i] = fib(i);
        return t;
    }();                                        // the table is built while compiling
    for (auto v : table) std::cout << v << ' ';
    std::cout << '\n';
}

Related: C++ Recursion.

C++ Factorial Program: Loop, Recursion and Overflow

The factorial of n is n x (n-1) x ... x 1. For example 5! = 120. It grows very fast.

Loop and recursion

#include <iostream>

unsigned long long factorial_loop(int n) {
    unsigned long long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

unsigned long long factorial_rec(int n) {
    return n <= 1 ? 1 : n * factorial_rec(n - 1);
}

int main() {
    std::cout << factorial_loop(5) << '\n';
    std::cout << factorial_rec(10) << '\n';
    std::cout << factorial_loop(20) << '\n';      // the biggest that fits in 64 bits
    std::cout << factorial_loop(21) << '\n';      // overflow: it wraps around, no error
}

Detect the overflow

The compiler has a built in check for overflow:

#include <iostream>
#include <optional>

std::optional<unsigned long long> safe_factorial(int n) {
    unsigned long long result = 1;
    for (int i = 2; i <= n; i++) {
        if (__builtin_mul_overflow(result, static_cast<unsigned long long>(i), &result)) {
            return std::nullopt;
        }
    }
    return result;
}

int main() {
    for (int n : {5, 20, 21, 25}) {
        if (auto f = safe_factorial(n)) std::cout << n << "! = " << *f << '\n';
        else std::cout << n << "! does not fit in 64 bits\n";
    }
}

Compile time factorial

#include <iostream>

constexpr unsigned long long factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}

int main() {
    constexpr auto f10 = factorial(10);
    static_assert(f10 == 3628800);               // checked while compiling
    std::cout << f10 << '\n';
}

For bigger numbers you need a big integer library (like Boost.Multiprecision or GMP), because C++ has no built in big integer type. Related: C++ Recursion and C++ Data Types.

C++ Armstrong Number Program

An Armstrong number equals the sum of its digits, each raised to the power of the number of digits. For example 153 = 1^3 + 5^3 + 3^3.

Program

#include <iostream>
#include <string>

int power(int base, int exponent) {
    int result = 1;
    for (int i = 0; i < exponent; i++) result *= base;
    return result;
}

bool is_armstrong(int number) {
    int digits = static_cast<int>(std::to_string(number).size());
    int sum = 0, n = number;
    while (n > 0) {
        sum += power(n % 10, digits);
        n /= 10;
    }
    return sum == number;
}

int main() {
    std::cout << std::boolalpha << is_armstrong(153) << ' ' << is_armstrong(154) << ' ' << is_armstrong(9474) << '\n';

    std::cout << "Armstrong numbers up to 1000: ";
    for (int i = 1; i <= 1000; i++) {
        if (is_armstrong(i)) std::cout << i << ' ';
    }
    std::cout << '\n';
}

How it works

• std::to_string(number).size() counts the digits.
• The loop takes the last digit with % 10 and adds its power.
• We wrote our own integer power, because std::pow works with decimals and can give a small rounding error.

Related: C++ while Loop.

C++ Program to Read a CSV File and Calculate the Total

CSV files are everywhere. This program reads a small sales file, skips the header, ignores bad lines and shows the total and the average.

Program

#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>

struct Sale {
    std::string item;
    int quantity;
    double price;
    double amount() const { return quantity * price; }
};

std::vector<std::string> split(const std::string& line, char sep) {
    std::vector<std::string> parts;
    std::istringstream in(line);
    std::string part;
    while (std::getline(in, part, sep)) parts.push_back(part);
    return parts;
}

int main() {
    std::ofstream("sales.csv") << "item,quantity,price\nPen,10,5.50\nBook,2,250\nBag,1,899.99\nBroken line\nNotebook,abc,40\n";

    std::ifstream in("sales.csv");
    std::string line;
    std::getline(in, line);                             // skip the header

    std::vector<Sale> sales;
    while (std::getline(in, line)) {
        auto p = split(line, ',');
        if (p.size() != 3) {
            std::cout << "Skipped (wrong columns): " << line << '\n';
            continue;
        }
        try {
            sales.push_back({p[0], std::stoi(p[1]), std::stod(p[2])});
        } catch (const std::exception&) {
            std::cout << "Skipped (bad number): " << line << '\n';
        }
    }

    double total = 0;
    std::cout << std::fixed << std::setprecision(2);
    for (const auto& s : sales) {
        std::cout << std::left << std::setw(10) << s.item << std::right << std::setw(8) << s.amount() << '\n';
        total += s.amount();
    }
    std::cout << "Total: " << total << '\n';
    std::cout << "Average per row: " << total / sales.size() << '\n';
}

Notes

• std::getline(in, part, ',') splits a text by a character.
• std::stoi and std::stod throw an exception for a bad number, so we catch it and skip the line.
• If a value can contain a comma inside quotes, use a CSV library.

Related: C++ File Handling and C++ Exceptions.

C++ Singly Linked List with unique_ptr

A linked list is a chain of nodes, where every node keeps a value and a pointer to the next node. This version uses std::unique_ptr, so there is no delete and no memory leak.

Program

#include <iostream>
#include <memory>
#include <utility>

class LinkedList {
    struct Node {
        int value;
        std::unique_ptr<Node> next;
        explicit Node(int v) : value(v) {}
    };
public:
    void push_front(int v) {
        auto node = std::make_unique<Node>(v);
        node->next = std::move(head);
        head = std::move(node);
        count++;
    }

    void push_back(int v) {
        auto node = std::make_unique<Node>(v);
        if (!head) { head = std::move(node); count++; return; }
        Node* cur = head.get();
        while (cur->next) cur = cur->next.get();
        cur->next = std::move(node);
        count++;
    }

    bool contains(int v) const {
        for (const Node* cur = head.get(); cur; cur = cur->next.get())
            if (cur->value == v) return true;
        return false;
    }

    bool remove(int v) {
        std::unique_ptr<Node>* link = &head;
        while (*link) {
            if ((*link)->value == v) {
                *link = std::move((*link)->next);
                count--;
                return true;
            }
            link = &(*link)->next;
        }
        return false;
    }

    void reverse() {
        std::unique_ptr<Node> prev;
        while (head) {
            auto next = std::move(head->next);
            head->next = std::move(prev);
            prev = std::move(head);
            head = std::move(next);
        }
        head = std::move(prev);
    }

    void print() const {
        for (const Node* cur = head.get(); cur; cur = cur->next.get())
            std::cout << cur->value << (cur->next ? " -> " : "");
        std::cout << '\n';
    }

    std::size_t size() const { return count; }

private:
    std::unique_ptr<Node> head;
    std::size_t count = 0;
};

int main() {
    LinkedList list;
    list.push_back(2);
    list.push_back(3);
    list.push_front(1);
    list.print();

    std::cout << list.contains(3) << ' ' << list.contains(9) << ' ' << list.size() << '\n';
    list.remove(2);
    list.print();
    list.push_back(4);
    list.reverse();
    list.print();
}

Notes

• The nodes are owned by their previous node. When the list is destroyed, the chain is deleted by the destructors. (Very long lists can overflow the stack in that recursive destruction, so a production list deletes the nodes in a loop.)
• In real code use std::list or, much better, std::vector. Writing a list is a good way to learn pointers.

Related: Smart Pointers and C++ Pointers.

C++ Random Numbers with mt19937 and uniform_int_distribution

Do not use rand(). It is old, of low quality and has a bad range. Modern C++ uses a generator (an engine) and a distribution from <random>.

A dice and a decimal number

#include <iostream>
#include <random>

int main() {
    std::random_device device;                          // a true random seed, if the system has it
    std::mt19937 gen(device());                         // the engine (Mersenne Twister)

    std::uniform_int_distribution<int> dice(1, 6);
    std::uniform_real_distribution<double> unit(0.0, 1.0);

    bool all_ok = true;
    for (int i = 0; i < 1000; i++) {
        int d = dice(gen);
        double u = unit(gen);
        all_ok = all_ok && d >= 1 && d <= 6 && u >= 0.0 && u < 1.0;
    }
    std::cout << "1000 numbers, all in range: " << all_ok << '\n';
}

Every run gives different numbers, so we only check the range. When you run it, print dice(gen) to see them.

A fixed seed: the same numbers every time

For tests and games with a “seed”, give the engine a number. The mt19937 engine is exactly defined by the standard, so its raw numbers are the same everywhere:

#include <iostream>
#include <random>

int main() {
    std::mt19937 a(42);
    std::cout << a() << ' ' << a() << ' ' << a() << '\n';

    std::mt19937 c(42), d(42);                         // two engines with the same seed
    std::cout << std::boolalpha << (c() == d()) << ' ' << (c() == d()) << '\n';
}

The distributions (like uniform_int_distribution) can give different numbers on different compilers, even with the same seed. Only the engine is fully fixed.

Shuffle and pick

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::vector<int> cards = {1, 2, 3, 4, 5, 6, 7, 8};
    std::mt19937 gen(std::random_device{}());

    std::shuffle(cards.begin(), cards.end(), gen);
    std::cout << cards.size() << " cards, sorted again: ";
    std::sort(cards.begin(), cards.end());
    for (int c : cards) std::cout << c << ' ';
    std::cout << '\n';

    std::uniform_int_distribution<std::size_t> pick(0, cards.size() - 1);
    std::cout << "random index in range: " << (pick(gen) < cards.size()) << '\n';
}

Good to know

• Create the engine once and reuse it. Do not make a new one for every number.
• mt19937 is not safe for passwords or keys. For security use the random functions of the operating system or a crypto library.
• std::random_device can be weak on some old systems.

Related: C++ Algorithms and C++ Vectors.