// diana.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <string>
#include <queue>
#include <stack>

using namespace std;

struct node {
    int val;
    node* next;

    node() noexcept : val(-1), next(nullptr)
    {
    }

    node(int val, node* next) noexcept : val(val), next(next)
    {
    }
};

struct tree {
    int val;
    tree* left;
    tree* right;

    tree() noexcept : val(-1), left(nullptr), right(nullptr)
    {
    }

    tree(int val, tree* left, tree* right) noexcept : val(val), left(left), right(right)
    {
    }
};

//1 - sa se verifice daca un sir de paranteze este parantezat corect
//folosesti un stack
bool paran(const string& p) {
    stack<char> s;
    for (char c : p) {
        if (c == '(') {
            s.push(c);
        }
        if (c == ')') {
            if (s.empty()) return false;
            s.pop();
        }
    }
    return !s.empty();
}

//2 - sa se verifice daca 2 numere dintr-un vector dau suma target si sa se intoarca indexii lor
//exista mai multe solutii eficiente si mai putin eficiente. poti totusi sa vorbesti despre 3 dintre ele
//1) 2 foruri, evident
//2) sortezi vectorul si cand esti pe un element x vrei sa cautid target-x si pentru ca este sortat
//poti sa il cauti binar
//3) nu sortezi vectorul si folosesti un hashtable ca sa cauti target-x
pair<int, int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> m;
    for (int i = 0; i < (int)nums.size(); ++i) {
        const auto it = m.find(target - nums[i]);
        if (it != m.end()) {
            return { it->second, i };
        }
        m[nums[i]] = i;
    }
    return { -1, -1 };
}

//sa se inverseze o lista inlantuita
//aic este destul de evident dar ce este foarte important este sa faci
//totul in-place adica sa nu aloci memorie noua
//vrei daor sa inversezi directia acelor arce imaginare din lista
void reverse_list(node** head) {
    node* l = *head;
    node* rev = NULL;
    while (l) {
        node* cur = l;
        l = l->next;
        cur->next = rev;
        rev = cur;
    }
    *head = rev;
}

//gaseste mijlocul unei liste inlantuite
//este ce am disccutat cu cei 2 pointeri cu viteze diferite
node* middle_list(node* head) {
    node* p = head;
    node* q = head;
    while (q && q->next) {
        p = p->next;
        q = q->next->next;
    }
    return p;
}

//gasete daca o lista are ciclu in ea
//am discutat si asta
bool has_cycle(node* head) {
    if (!head) {
        return false;
    }
    node* p = head;
    node* q = head;

    do {
        p = p->next;
        q = q->next->next;
        if (p == q) return true;
    } while (q && q->next);
    return false;
}

//prima aparitie a lui 1 intr-o lista plina cu 0 si 1 cu 0-uri la inceput
//si 1 la final
//oricand vezi ca vectorul este sortat in vreun fel e o idee buna sa te gandesti
//prima oara la cautare binara
int find_first_one(const vector<int>& nums) {
    int s = (int)nums.size();
    int l = 0, r = s;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        if (nums[mid] == 0) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return l;
}

//sa faci intr-un sir minimul de schimbari ca sa fie toate caracterele
//adiacente diferite
//aici spre exeplu daca ai aaabbb -> vrei sa schimbi a-ul din mijloc
//si b-ul din mijloc
//daca ai abb -> vrei sa schimbi un singur b
//observam ca ne intereseaza doar alea de caractere egale continue - sunt independente intre ele
//daca avem aaa -> 1 si pentu aaaa -> 4 => destul de evident ca daca sunt x egale trb sa schimbam
//x / 2
int minimum_changes(const string& s) {
    int cur_block = 1;
    int r = 0;
    for (int i = 1; i < (int)s.size(); ++i) {
        if (s[i] == s[i - 1]) {
            ++cur_block;
        } else {
            r += cur_block / 2;
            cur_block = 1;
        }
    }
    r += cur_block / 2;
}

// sir de paranteze unde poti avea (, [ si {
//la fel ca ala paran1 dar aici trb sa te uiti si ca varful stackului
//sa dea match cu ce tip de paranteza ai tu
bool paran(const string& p) {
    stack<char> s;
    for (char c : p) {
        if (c == '(' || c == '{' || c == '[') {
            s.push(c);
        }
        if (c == ')') {
            if (s.empty() || s.top() != '(') return false;
            s.pop();
        }
        if (c == ']') {
            if (s.empty() || s.top() != '[') return false;
            s.pop();
        }
        if (c == '}') {
            if (s.empty() || s.top() != '{') return false;
            s.pop();
        }
    }
    return !s.empty();
}

//get hight of a tree
int h(tree* t) {
    if (!t) {
        return 0;
    }
    return 1 + max(h(t->left), h(t->right));
}

//traversare inorder recursiva
vector<int> inorder(tree* t) {
    if (!t) {
        return vector<int>();
    }
    vector<int> l = inorder(t->left);
    vector<int> r = inorder(t->right);
    l.push_back(t->val);
    l.insert(l.end(), r.begin(), r.end());
    return l;
}

//traversare inorder iterativa - se foloseste un stack pentru a vedea in ce apel de functie sunt
//este putin tricky pentru ca atunci cand sunt intr un nod trebuie sa fac 3 chestii in ordinea asta
//apeleaza pentru left, printeaza elementul, apeleaza pentru right
//solutie: pun mereu in stack 2 duplicate ale fiecarui element, cand este prima oara cand il scot din stack
//inseamna ca abia am intrat in nod si trebuie sa apelez pentru stranga deci pun si stanga in stack
//cand este a 2a oara cand l am scos din stack inseamna ca il pot printa si continua procesul pentru dreapta
// de ce este mai bine iterativ decat recursiv? simplu, nu mai am apeluri pe stack

vector<int> inorder(tree* t) {
    if (!t) {
        return vector<int>();
    }
    const int call_left = 1;
    const int call_right = 1;
    vector<int> r;
    stack<pair<tree*, int>> s;
    s.emplace(t, call_right);
    s.emplace(t, call_left);

    while (!s.empty()) {
        const auto p = s.top();
        const tree* tr = p.first;
        if (p.second == call_left) {
            s.emplace(tr->left, call_right);
            s.emplace(tr->left, call_left);
        }
        else {
            r.push_back(p.first->val);
            s.emplace(tr->right, call_right);
            s.emplace(tr->right, call_left);
        }
    }
    return r;
}

//postordinea si alte traversari se fac dupa aceeasi idee

// ai 2 multimi A si B si B este inclusa in A dar A contine cu un element mai mult - care este acel element
//aici exista mai multe solutii - una dintre ele este sa faci suma elementelor din A si dupa sa scazi
//suma elementelor din B
//sau poti face xor

int missing_element(const vector<int>& a, const vector<int>& b) {
    int el = 0;
    for (const int e : a) {
        el ^= e;
    }
    for (const int e : b) {
        el ^= e;
    }
    return el;
}


//zig zag traverrsal
//punem intr-un stack nivelul curent cu dorectioa care trebuie
//din stanga sau din dreapta
//si apoi folosim un nou stack pentru obtine nivelul urmator in directia
//opusa
vector<vector<int>> zigzagLevelOrder(tree* root) {
    vector<vector<int>> r;
    stack<tree*> s;
    s.push(root);
    int lev = 0;
    while (s.empty() == false) {
        vector<int> level;
        lev = 1 - lev;
        stack<tree*> aux_s;
        while (s.empty() == false) {
            auto t = s.top();
            s.pop();
            if (!t) {
                continue;
            }
            level.push_back(t->val);
            if (lev) {
                aux_s.push(t->left);
                aux_s.push(t->right);
            }
            else {
                aux_s.push(t->right);
                aux_s.push(t->left);
            }
        }
        if (level.size()) {
            r.push_back(level);
        }
        s = aux_s;
    }
    return r;
}

//cele mai mici k elemente dintr un vector
//solutie trebuie sa mentinem o structura de dimensiune k
//care sa retina cele mai mici k numere
//cand vine un numar nou vrem sa il comparam cu maximul
//daca este mai mic dect maximul din cele k atunci maximul trebuie inlocuit cu elmentul curent
//ce structura de date trebuie folosita ca sa vedem repede maximul si sa il eliminam?
//heapul este o structura buna pentru asta
//complexitate O(nlog(k))
vector<int> first_k(const vector<int>& nums, int k) {
    vector<int> r;
    priority_queue<int> p;
    for (int i = 0; i < k; ++i) {
        p.push(nums[i]);
    }
    for (int i = k; i < (int)nums.size(); ++i) {
        if (p.top() > nums[i]) {
            p.pop();
            p.push(nums[i]);
        }
    }
    while (!p.empty()) {
        r.push_back(p.top());
        p.pop();
    }
    return r;
}

//vrei sa vezi daca un nuamr este putee de 2
//solutia 1 tot imparti la 2 pana obtii 1 sau ceva de genul
//este log(n) dar se poate si mai bine cu o singura operatie pe biti
//n & (n - 1) == 0, daca se intampla asta atunci este putere de 2 altfel nu

bool is_two_power(int n) {
    return (n & (n - 1)) == 0;
}

//vrei sa numeri cati biti de 1 are un numar setat
//o solutie ar fi sa iterezi peste toti bitii(32) si sa vezi cati sunt setati
//alta solutie este sa analizezi din nou expresia (n & (n - 1)) si sa vezi ce face
//asta elimina cel mai putin semnificant bit din numar adica pentru numarul
//11100110 il va transforam in 11100100, poti sa iti iei o foaie cu mai multe
//exemple ca sa vezi ca este asa

//aici numarul de operatii pe care il faci este fix numarul de 1 pe care
//il are numarul scris in binar
int count_bits(int n) {
    int r = 0;
    while (n) {
        ++r;
        n = (n & (n - 1));
    }
    return r;
}

//mai putin eficient in log(n)
int count_bits(int n) {
    int r = 0;
    for (int i = 0; i < 31; ++i) {
        if (n & (1 << i)) {
            ++r;
        }
    }
    return r;
}

//vrei sa vezi daca 2 stringuri sunt anagragem
//adica au caracterele la fel dar permutate
//folosim vectori de aparitie
bool anagram(const string& a, const string& b) {
    const int alph_size = 'z' - 'a' + 1;
    vector<int> aocc(alph_size, 0);
    vector<int> bocc(alph_size, 0);
    for (const char c : a) {
        aocc[c - 'a']++;
    }
    for (const char c : b) {
        bocc[c - 'b']++;
    }
    for (int i = 0; i < (int)aocc.size(); ++i) {
        if (aocc[i] != bocc[i]) return false;
    }
    return true;
}

int main()
{
    std::cout << "Hello World!\n";
}