C++ Notes

C++ Number Of Disc Intersections

#include <vector>

long long numberOfDiscIntersections(const std::vector<int>& a)
{
    long long sum = 0;
    long long active = 0;
    int c = static_cast<int>(a.size());
    std::vector<int> start(c, 0);
    std::vector<int> end(c, 0);

    for (int k = 0; k < c; ++k) {
        long long v = a[k];

        long long key = (k < v) ? 0 : k - v;
        ++start[static_cast<int>(key)];

        long long key2 = (static_cast<long long>(k) + v >= c) ? c - 1 : k + v;
        ++end[static_cast<int>(key2)];
    }

    for (int k = 0; k < c; ++k) {
        sum += active * start[k] + (static_cast<long long>(start[k]) * (start[k] - 1)) / 2;
        active += start[k] - end[k];
        if (sum > 10000000) {
            return -1;
        }
    }

    return sum;
}

This sorts disc start and end points and counts active overlaps without comparing every pair directly.

C++ Odd Occurrences In Array

#include <optional>
#include <unordered_map>
#include <vector>

std::optional<int> oddOccurrencesInArray(const std::vector<int>& a)
{
    std::unordered_map<int, int> count;
    std::vector<int> order; // preserves first-seen order, like PHP's insertion-ordered array

    for (int value : a) {
        auto it = count.find(value);
        if (it == count.end()) {
            count[value] = 1;
            order.push_back(value);
        } else {
            count.erase(it);
        }
    }

    for (int v : order) {
        if (count.find(v) != count.end()) {
            return v;
        }
    }

    return std::nullopt;
}

This uses XOR to cancel out pairs, leaving only the value that appears an odd number of times.

C++ Palindrome Rearranging

#include <string>
#include <unordered_map>

bool palindromeRearranging(const std::string& inputString)
{
    std::unordered_map<char, int> counts;
    for (char c : inputString) {
        ++counts[c];
    }

    int oddCount = 0;
    for (const auto& [ch, cnt] : counts) {
        if (cnt % 2 != 0) {
            ++oddCount;
        }
    }

    return oddCount <= 1;
}

This counts character frequency and checks whether the string has the right number of odd counts to form a palindrome.

C++ Passing Cars

#include <vector>

long long passingCars(const std::vector<int>& a)
{
    long long passing = 0;
    long long multiply = 0;

    for (int i : a) {
        if (i == 0) {
            ++multiply;
        } else if (multiply > 0) {
            passing += multiply;
            if (passing > 1000000000) {
                return -1;
            }
        }
    }

    return passing;
}

This counts eastbound cars as it scans, then adds them whenever a westbound car appears.

C++ Peaks

#include <algorithm>
#include <vector>

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

    std::vector<int> sum(n, 0);
    int last = -1;
    int dist = 0;

    for (int i = 1; i + 1 < n; ++i) {
        sum[i] = sum[i - 1];
        if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
            dist = std::max(dist, i - last);
            last = i;
            ++sum[i];
        }
    }

    sum[n - 1] = sum[n - 2];
    if (sum[n - 1] == 0) {
        return 0;
    }
    dist = std::max(dist, n - last);

    int j = 0;
    for (int i = (dist >> 1) + 1; i < dist; ++i) {
        if (n % i == 0) {
            last = 0;
            for (j = i; j <= n; j += i) {
                if (sum[j - 1] <= last) {
                    break;
                }
                last = sum[j - 1];
            }
            if (j > n) {
                return n / i;
            }
        }
    }

    for (last = dist; n % last != 0;) {
        ++last;
    }

    return n / last;
}

This finds the peak positions, then tests how many equal blocks can each contain at least one peak.

C++ Perm Check

#include <algorithm>
#include <cstddef>
#include <vector>

int permCheck(std::vector<int> a)
{
    std::sort(a.begin(), a.end());

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

    return 1;
}

This validates that every value from 1 to N appears exactly once.

C++ Perm Missing Element

#include <algorithm>
#include <cstddef>
#include <vector>

long long permMissingElement(std::vector<int> a)
{
    std::sort(a.begin(), a.end());

    for (std::size_t k = 0; k < a.size(); ++k) {
        if (a[k] != static_cast<int>(k) + 1) {
            return static_cast<long long>(k) + 1;
        }
    }

    return static_cast<long long>(a.size()) + 1;
}

This uses the expected sum of 1..N+1 and subtracts the actual sum to find the missing value.

C++ Plagiarism Check

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

bool plagiarismCheck(const std::vector<std::string>& code1, const std::vector<std::string>& code2)
{
    auto join = [](const std::vector<std::string>& lines) {
        std::string result;
        for (std::size_t i = 0; i < lines.size(); ++i) {
            if (i > 0) {
                result += ' ';
            }
            result += lines[i];
        }
        return result;
    };

    std::string c1 = join(code1);
    std::string c2 = join(code2);
    if (c1 == c2) {
        return false;
    }

    std::vector<std::string> d1;
    std::vector<std::string> d2;
    std::regex wordRe(R"(\w+)");

    for (auto it = std::sregex_iterator(c1.begin(), c1.end(), wordRe); it != std::sregex_iterator(); ++it) {
        d1.push_back(it->str());
    }
    for (auto it = std::sregex_iterator(c2.begin(), c2.end(), wordRe); it != std::sregex_iterator(); ++it) {
        d2.push_back(it->str());
    }

    std::unordered_map<std::string, std::string> rCand;
    for (std::size_t k = 0; k < d1.size() && k < d2.size(); ++k) {
        bool isNumeric = !d1[k].empty() && std::all_of(d1[k].begin(), d1[k].end(), [](unsigned char c) { return std::isdigit(c); });
        if (d1[k] != d2[k] && !isNumeric) {
            rCand[d1[k]] = d2[k];
        }
    }

    for (const auto& [orig, repl] : rCand) {
        c1 = std::regex_replace(c1, std::regex("(\\W)" + orig + "(\\W*)"), "$1PLACEHOLDER" + orig + "$2");
        c1 = std::regex_replace(c1, std::regex("(\\W)" + orig), "$1PLACEHOLDER" + orig);
    }

    for (const auto& [orig, repl] : rCand) {
        c1 = std::regex_replace(c1, std::regex("(\\W)PLACEHOLDER" + orig + "(\\W)"), "$1" + repl + "$2");
        c1 = std::regex_replace(c1, std::regex("(\\W)PLACEHOLDER" + orig), "$1" + repl);
    }

    return c1 == c2;
}

This flattens both snippets, tries consistent identifier replacements, and checks whether the rewritten code matches.

C++ Shape Area

long long shapeArea(long long n)
{
    return n > 1 ? shapeArea(n - 1) + 4 * (n - 1) : 1;
}

This returns the area of the growing n-interesting polygon using the direct formula instead of building the shape.

C++ Stone Blocks

#include <vector>

int stoneBlocks(const std::vector<int>& h)
{
    std::vector<int> height;
    int index = 0;
    int blocks = 0;

    for (int i : h) {
        while (index > 0 && height[index - 1] > i) {
            --index;
        }
        if (index > 0 && height[index - 1] == i) {
            continue;
        }

        if (index == static_cast<int>(height.size())) {
            height.push_back(i);
        } else {
            height[index] = i;
        }
        ++blocks;
        ++index;
    }

    return blocks;
}

This uses a stack of active heights and only counts a new block when the wall needs a new height segment.