C++ Notes

C++ Dominator

#include <cstddef>
#include <vector>

int dominator(const std::vector<int>& a)
{
    int size = 0;
    int value = 0;
    int index = 0;

    for (std::size_t k = 0; k < a.size(); ++k) {
        int v = a[k];
        if (size == 0) {
            ++size;
            value = v;
            index = static_cast<int>(k);
        } else if (value != v) {
            --size;
        } else {
            ++size;
        }
    }

    int candidate = size > 0 ? value : -1;
    int count = 0;
    for (int v : a) {
        if (v == candidate) {
            ++count;
        }
    }
    if (count <= static_cast<int>(a.size()) / 2) {
        index = -1;
    }

    return index;
}

This finds a value that appears in more than half of the array, then returns one valid index for it.

C++ Equi Leader

#include <vector>

int equiLeader(const std::vector<int>& a)
{
    int leaderSize = 0;
    int value = 0;
    for (int v : a) {
        if (leaderSize == 0) {
            ++leaderSize;
            value = v;
        } else if (value != v) {
            --leaderSize;
        } else {
            ++leaderSize;
        }
    }
    int candidate = leaderSize > 0 ? value : -1;

    int leaderCount = 0;
    for (int v : a) {
        if (v == candidate) {
            ++leaderCount;
        }
    }

    int count = static_cast<int>(a.size());
    int leader = -1;
    if (leaderCount > count / 2) {
        leader = candidate;
    }

    int lLeaderCount = 0;
    int equiLeaders = 0;

    for (int k = 0; k < count; ++k) {
        int v = a[k];
        int leftHalf = (k + 1) / 2;
        int rightHalf = (count - k - 1) / 2;
        if (v == leader) {
            ++lLeaderCount;
        }

        int rLeaderCount = leaderCount - lLeaderCount;
        if (lLeaderCount > leftHalf && rLeaderCount > rightHalf) {
            ++equiLeaders;
        }
    }

    return equiLeaders;
}

This keeps leader counts on both sides of the split and counts positions where the same leader survives in each half.

C++ Fib Frog

#include <queue>
#include <vector>

int fibFrog(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());

    std::vector<int> fib{0, 1};
    for (int i = 1; fib[i] <= size;) {
        ++i;
        fib.push_back(fib[i - 1] + fib[i - 2]);
    }

    struct Path {
        int idx;
        int jmp;
    };

    std::queue<Path> paths;
    paths.push({-1, 0});

    std::vector<bool> steps(size, false);

    while (!paths.empty()) {
        Path path = paths.front();
        paths.pop();

        for (int i = static_cast<int>(fib.size()) - 1; i >= 2; --i) {
            int idx = path.idx + fib[i];
            if (idx == size) {
                return path.jmp + 1;
            }
            if (idx > size || steps[idx] || a[idx] == 0) {
                continue;
            }
            if (a[idx] == 1) {
                steps[idx] = true;
                paths.push({idx, path.jmp + 1});
            }
        }
    }

    return -1;
}

This precomputes Fibonacci jumps, then uses a breadth-first search to find the shortest valid path across the river.

C++ Fish

#include <vector>

int fish(const std::vector<int>& a, const std::vector<int>& b)
{
    int size = static_cast<int>(a.size());
    int dead = 0;
    std::vector<int> downstream;

    for (int i = 0; i < size; ++i) {
        if (b[i] == 1) {
            downstream.push_back(a[i]);
        } else if (!downstream.empty()) {
            while (!downstream.empty()) {
                ++dead;
                if (a[i] > downstream.back()) {
                    downstream.pop_back();
                } else {
                    break;
                }
            }
        }
    }

    return size - dead;
}

This uses a stack for downstream fish and resolves fights only when opposite directions meet.

C++ Flags

#include <algorithm>
#include <vector>

int flags(const std::vector<int>& a)
{
    int size = static_cast<int>(a.size());
    if (size == 0) {
        return 0;
    }

    std::vector<bool> peaks(size, false);
    for (int i = 1; i < size; ++i) {
        int nextVal = (i + 1 < size) ? a[i + 1] : 0;
        peaks[i] = a[i - 1] < a[i] && a[i] > nextVal;
    }

    std::vector<int> next(size);
    next[size - 1] = -1;
    for (int i = size - 2; i >= 0; --i) {
        next[i] = peaks[i] ? i : next[i + 1];
    }

    int i = 1;
    int result = 0;
    while (i * (i - 1) <= size) {
        int pos = 0;
        int num = 0;
        while (pos < size && num < i) {
            pos = next[pos];
            if (pos == -1) {
                break;
            }
            ++num;
            pos += i;
        }
        ++i;
        result = std::max(result, num);
    }

    return result;
}

This finds all peaks first, then checks how many flags can be placed while keeping the required distance.

C++ Frog Jmp

#include <cmath>

long long frogJmp(long long x, long long y, long long d)
{
    return static_cast<long long>(std::ceil(static_cast<double>(y - x) / d));
}

This computes the jump count with math instead of simulation, which is the cleanest way to solve it.

C++ Frog River One

#include <cstddef>
#include <vector>

int frogRiverOne(int x, const std::vector<int>& a)
{
    std::vector<bool> existing(x + 1, false);
    int count = 0;

    for (std::size_t k = 0; k < a.size(); ++k) {
        int i = a[k];
        if (i <= x && !existing[i]) {
            existing[i] = true;
            ++count;
            if (count == x) {
                return static_cast<int>(k);
            }
        }
    }

    return -1;
}

This tracks the earliest time each needed position appears and stops as soon as the frog can cross.

C++ Genomic Range Query

#include <cstddef>
#include <string>
#include <vector>

std::vector<int> genomicRangeQuery(const std::string& s, const std::vector<int>& p, const std::vector<int>& q)
{
    std::vector<int> r;
    r.reserve(p.size());

    for (std::size_t k = 0; k < p.size(); ++k) {
        int pi = p[k];
        int qi = q[k] - pi + 1;
        std::string subStr = s.substr(pi, qi);

        if (subStr.find('A') != std::string::npos) {
            r.push_back(1);
        } else if (subStr.find('C') != std::string::npos) {
            r.push_back(2);
        } else if (subStr.find('G') != std::string::npos) {
            r.push_back(3);
        } else {
            r.push_back(4);
        }
    }

    return r;
}

This builds prefix counts for each DNA letter so every query can return the minimum impact factor quickly.

C++ Is Ipv 4 Adress

#include <algorithm>
#include <cctype>
#include <string>
#include <vector>

bool isIPv4Address(const std::string& inputString)
{
    std::vector<std::string> parts;
    std::string cur;
    for (char c : inputString) {
        if (c == '.') {
            parts.push_back(cur);
            cur.clear();
        } else {
            cur += c;
        }
    }
    parts.push_back(cur);

    for (const auto& v : parts) {
        if (v.empty() || !std::all_of(v.begin(), v.end(), [](unsigned char c) { return std::isdigit(c); })) {
            return false;
        }
        if (v.size() > 1 && v[0] == '0') {
            return false; // rejects leading zeros, mirrors $v !== (string)(int)$v
        }
        if (std::stol(v) > 255) {
            return false;
        }
    }

    return parts.size() == 4;
}

This splits the string by dots and validates each part as a normal IPv4 octet.

C++ Ladder

#include <algorithm>
#include <vector>

std::vector<int> ladder(const std::vector<int>& a, const std::vector<int>& b)
{
    std::size_t size = a.size();
    std::vector<int> r(size, 0);

    int maxB = *std::max_element(b.begin(), b.end());
    long long mod = (1LL << maxB) - 1;

    int maxA = *std::max_element(a.begin(), a.end());
    std::vector<long long> fib(maxA + 2, 0);
    fib[1] = 1;
    for (int i = 2; i < maxA + 2; ++i) {
        fib[i] = (fib[i - 1] + fib[i - 2]) & mod;
    }

    for (std::size_t i = 0; i < size; ++i) {
        r[i] = static_cast<int>(fib[a[i] + 1] & ((1LL << b[i]) - 1));
    }

    return r;
}

This precomputes climb counts once and applies the modulo per query, which avoids recalculating the same paths over and over.