lcpz

// https://projecteuler.net/problem=347

#include <vector>
#include <cmath>
#include <iostream>

std::vector getSieveOfEratosthenes(const int& n)
{
    if (n <= 0) return {};

lcpz

#!/usr/bin/env python3

"""
Returns the total stopping time of positive number n in the Collatz sequence.
"""
def collatz(n: int) -> bool:
    def get_next(n: int) -> int:
        return n % 2 == 0 and n//2 or (3*n + 1)//2
        """
        Shortcut: 3n + 1 is even if n is odd, so we can divide it by 2;

lcpz

/*
An improvement of the Disjoint-Set Forest is to control tree heights storing in each node
its rank, which is an upper bound for its height. When a node is initialized, its rank is
set to zero. To merge trees with roots x and y, first compare their ranks. If the ranks
are different, then the larger rank tree becomes the parent, and the ranks of x and y do
not change. If the ranks are the same, then either one can become the parent, but the new
parent's rank is incremented by one. While the rank of a node is clearly related to its
height, storing ranks is more efficient than storing heights. The height of a node can
change during a Find operation, so storing ranks avoids the extra effort of keeping the
height correct. This method ensures that trees do not become too deep.

lcpz

// https://leetcode.com/problems/merge-k-sorted-lists

/*
 * O(N log k) time and O(1) space, where N is the total number of nodes.
 *
 * # Explanation of the time complexity
 *
 * Let n be an upper bound on the number of nodes of each list.
 *
 * We iteratively merge pairs of lists as follows:

lcpz

// https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string

/*
 * # Brute force approach
 *
 * Generate all substrings, and count the unique chars in each.
 *
 * Time complexity: O(n^2) to generate all substrings, O(n) to count unique chars for
 * each. Total: O(n^3).
 *

lcpz

// https://leetcode.com/problems/median-of-two-sorted-arrays

// https://www.youtube.com/watch?v=LPFhl65R7ww
// https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2471/Very-concise-O(log(min(MN)))-iterative-solution-with-detailed-explanation

class Solution {
public:
    double findMedianSortedArrays(vector<int>& a1, vector<int>& a2) {
        if (a1.size() > a2.size()) swap(a1, a2); // ensure a1 is shorter

lcpz

// https://leetcode.com/problems/split-array-largest-sum

// Same as https://www.codingninjas.com/codestudio/library/book-allocation-problem

class Solution {
public:
    /*
     * Let dp[i][j + 1] be the an optimal solution to the subproblem with i subarrays within
     * A[0..j]. Let sum[i][j] be the sum of the numbers in A[i..j]. Then:
     *

lcpz

class Solution {
    int getPivotIndex(int& l, int& r) {
        return l + (r - l) / 2;
        //return l + rand() % (r - l + 1);
    }
    
    int partition(vector<int>& A, int& l, int& r) {
        int i = l, pivotIndex = getPivotIndex(l, r), pivot = A[pivotIndex];
        
        swap(A[pivotIndex], A[r]);

lcpz

// https://leetcode.com/problems/implement-strstr

class Solution {
public:
    // Brute force, O((m - n) * n) worst and average case, O(n) best case
    int strStrNaive(const string& text, const string& pattern) {
        int m = text.size(), n = pattern.size();

        // be consistent with C/C++ strstr() and Java indexOf()
        if (!n) return 0;

lcpz

// https://leetcode.com/problems/find-median-from-data-stream

class MedianFinder {
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
public:
    void addNum(int num) {
        if (maxHeap.empty() || maxHeap.top() >= num)
            maxHeap.push(num);
        else