All.cc

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

// X raise to the power n, if n is double.
double myPow(double x, int n)
{
    double res = 1.0;
    if (n == 0)
        return 1;
    if (n < 0)
    {
        x = 1 / x;
        n = -n;
    }
    if (n % 2 == 0)
    {
        res = myPow(x, n / 2);
        return res * res;
    }
    else
    {
        res = myPow(x, n - 1);
        return x * res;
    }
    return 0;
}

// (x raised to y) mod p

//(m * n) % p has a very interesting property:
// (m * n) % p =((m % p) * (n % p)) % p

// Property 2:
// if b is even:
// (a ^ b) % c = ((a ^ b/2) * (a ^ b/2))%c ? this suggests divide and conquer
// if b is odd:
// (a ^ b) % c = (a * (a ^( b-1))%c
int exponentMod(int A, int B, int C)
{
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;

    long y;
    if (B % 2 == 0)
    {
        y = exponentMod(A, B / 2, C);
        y = (y * y) % C;
    }

    else
    {
        y = A % C;
        y = (y * exponentMod(A, B - 1, C) % C) % C;
    }
    return (int)((y + C) % C);
}

// Check if a number is prime.
bool checkPrime(int n)
{
    if (n == 1)
        return false;
    if (n < 4)
        return true;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

// Creates a sieve of eratosthenes.
vector<bool> SieveOfEratosthenes(int n)
{
    vector<bool> prime(n + 1, true);
    for (int p = 2; p * p <= n; p++)
    {
        if (prime[p] == true)
        {
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    return prime;
}

// Create a list of prime numbers upto n.
vector<int> listofprimes(int n)
{
    vector<int> primelist;
    vector<bool> v = SieveOfEratosthenes(n);
    for (int i = 2; i <= n; i++)
    {
        if (v[i])
            primelist.push_back(i);
    }
    return primelist;
}

// Create a list of prime factors of n.
vector<int> primefactors(int n)
{
    vector<int> factors;
    while (n % 2 == 0)
    {
        factors.push_back(2);
        n /= 2;
    }
    for (int i = 3; i * i <= n; i = i + 2)
    {
        while (n % i == 0)
        {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 2)
        factors.push_back(n);
    return factors;
}

// Returns the GCD of two number
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

// Returns the extended GCD of two numbers,
// x and y are coefficients of equation
// a*x + b*y = gcd(a,b)
int gcdExtended(int a, int b, int *x, int *y)
{
    if (a == 0)
    {
        *x = 0;
        *y = 1;
        return b;
    }

    int x1, y1;
    int gcd = gcdExtended(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}

// -1 no mod inverse
int modInverse(int a, int m)
{
    int x, y;
    int g = gcdExtended(a, m, &x, &y);
    if (g != 1)
        return -1;
    else
        return (x % m + m) % m;
}

// Returns the minimum number of coins need to make the given sum. Given sum and denominations.
int coinCount(vector<int> dens, int sum)
{
    sort(dens.rbegin(), dens.rend());
    int ans = 0;
    for (auto d : dens)
    {
        if (sum == 0)
            break;
        if (sum >= d)
        {
            ans += sum / d;
            sum %= d;
        }
    }
    return ans;
}

// Activity Scheduling Problem
bool comp(vector<int> &v1, vector<int> &v2)
{
    return v1[1] < v2[1];
}
// Return activities that can be held according to their start and end time.
vector<vector<int>> activity(vector<int> start, vector<int> finish)
{
    vector<vector<int>> meetings;
    for (int i = 0; i < start.size(); i++)
    {
        meetings.push_back({start[i], finish[i]});
    }
    sort(meetings.begin(), meetings.end(), comp);
    vector<vector<int>> ans;
    ans.push_back(meetings[0]);
    for (int i = 1; i < meetings.size(); i++)
    {
        if (ans[ans.size() - 1][1] <= meetings[i][0])
            ans.push_back(meetings[i]);
    }
    return ans;
}

// Count the number of digits in a number.
int countDigits(int n)
{
    int c = 0;
    while (n)
    {
        n /= 10;
        c++;
    }
    return c;
}

// Frugal Number
bool frugal(int n)
{
    vector<int> r = listofprimes(n);
    int t = n;
    // Finding number of digits in prime
    // factorization of the number
    int s = 0;
    for (int i = 0; i < r.size(); i++)
    {
        if (t % r[i] == 0)
        {

            // Exponent for current factor
            int k = 0;

            // Counting number of times this prime
            // factor divides (Finding exponent)
            while (t % r[i] == 0)
            {
                t = t / r[i];
                k++;
            }

            // Finding number of digits in the exponent
            // Avoiding exponents of value 1
            if (k == 1)
                s = s + countDigits(r[i]);
            else if (k != 1)
                s = s + countDigits(r[i]) + countDigits(k);
        }
    }
    // Checking condition for frugal number
    return (countDigits(n) > s && s != 0);
}

// K-Rough Number 1
bool isRough1(int n, int k)
{
    vector<int> primes = listofprimes(n);

    // Finding minimum prime factor of n
    int min_pf = n;
    for (int i = 0; i < primes.size(); i++)
        if (n % primes[i] == 0)
            min_pf = primes[i];

    // Return true if minimum prime factor
    // is greater than or equal to k. Else
    // return false.
    return (min_pf >= k);
}

// K-Rough Number 2
bool isKRough(int n, int k)
{
    // If n is even, then smallest prime
    // factor becomes 2.
    if (n % 2 == 0)
        return (k <= 2);

    // n must be odd at this point.  So we
    // can skip one element (Note i = i +2)
    for (int i = 3; i * i <= n; i = i + 2)
        if (n % i == 0)
            return (i >= k);

    return (n >= k);
}

// Maximum prime factor of n.
int maxPrimeFactors(int n)
{
    int maxPrime = -1;
    while (n % 2 == 0)
    {
        maxPrime = 2;
        n /= 2;
    }
    for (int i = 3; i < (int)(n * 1 / 2 + 1); i += 2)
        while (n % i == 0)
        {
            maxPrime = i;
            n /= i;
        }
    if (n > 2)
        maxPrime = n;
    return (int)(maxPrime);
}

bool isStormer(int n)
{
    return maxPrimeFactors(n * n + 1) >= 2 * n;
}

// Count number of divisors
int divCount(int n)
{
    // sieve method for prime calculation
    vector<bool> hash(n + 1, true);

    for (int p = 2; p * p < n; p++)
        if (hash[p] == true)
            for (int i = p * 2; i < n; i += p)
                hash[i] = false;

    // Traversing through all prime numbers
    int total = 1;
    for (int p = 2; p <= n; p++)
    {
        if (hash[p])
        {

            // calculate number of divisor
            // with formula total div =
            // (p1+1) * (p2+1) *.....* (pn+1)
            // where n = (a1^p1)*(a2^p2)....
            // *(an^pn) ai being prime divisor
            // for n and pi are their respective
            // power in factorization
            int count = 0;
            if (n % p == 0)
            {
                while (n % p == 0)
                {
                    n = n / p;
                    count++;
                }
                total = total * (count + 1);
            }
        }
    }
    return total;
}

// --------- Connect Sticks
int connectSticks(vector<int> sticks)
{

    priority_queue<int, vector<int>, greater<int>> pq;
    for (int a : sticks)
        pq.push(a);

    int sum = 0;
    while (pq.size() > 1)
    {
        int x = pq.top();
        pq.pop();
        int y = pq.top();
        pq.pop();
        sum += (x + y);
        pq.push(x + y);
    }
    return sum;
}

// ===== Knapsack ==== //
struct Item
{
    int value, weight;

    // Constructor
    Item(int value, int weight) : value(value), weight(weight)
    {
    }
};

// Comparison function to sort Item according to val/weight ratio
bool cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

// Main greedy function to solve problem.
double fractionalKnapsack(int W, struct Item arr[], int n)
{
    sort(arr, arr + n, cmp);

    int curWeight = 0;
    double finalvalue = 0.0;

    for (int i = 0; i < n; i++)
    {
        if (curWeight + arr[i].weight <= W)
        {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        }

        else
        {
            int remain = W - curWeight;
            finalvalue += arr[i].value * ((double)remain / arr[i].weight);
            break;
        }
    }
    // Returning final value
    return finalvalue;
}
// --------- END Knapsack

// Max Product Subarray
int maxProduct(vector<int> &nums)
{

    int n = nums.size();
    int maxpos = nums[0];
    int maxneg = nums[0];
    int maxval = nums[0];

    for (int i = 1; i < n; i++)
    {
        int a = maxpos * nums[i];
        int b = maxneg * nums[i];

        maxpos = max({a, b, nums[i]});
        maxneg = min({a, b, nums[i]});
        maxval = max(maxpos, maxval);
    }
    return maxval;
}

// Job sequence problem
void optimum_sequence_jobs(vector<int> &V, double P)
{
    int j = 1, N = V.size() - 1;
    double result = 0;

    priority_queue<int, vector<int>, greater<int>> Queue;

    for (int i = 1; i <= N; i++)
        Queue.push(V[i]);

    while (!Queue.empty())
    {

        cout << Queue.top() << " ";

        V[j++] = Queue.top();
        Queue.pop();
    }
    for (int i = N; i >= 1; i--)
        result += pow((1 - P), N - i) * V[i];

    // Print result
    cout << endl
         << result << endl;
}

// --------------- Job Scheduling ---------------
struct Job
{
    char id;
    int dead;
    int profit;
    Job(char id, int dead, int profit)
    {
        id = id;
        dead = dead;
        profit = profit;
    }
};

// This function is used for sorting all jobs according to profit
bool comparison(Job a, Job b)
{
    return (a.profit > b.profit);
}

// Returns minimum number of platforms reqquired
void printJobScheduling(vector<Job> &arr, int n)
{
    // Sort all jobs according to decreasing order of prfit
    sort(arr.begin(), arr.end(), comparison);

    int result[n]; // To store result (Sequence of jobs)
    bool slot[n];  // To keep track of free time slots

    // Initialize all slots to be free
    for (int i = 0; i < n; i++)
        slot[i] = false;

    // Iterate through all given jobs
    for (int i = 0; i < n; i++)
    {
        // Find a free slot for this job (Note that we start
        // from the last possible slot)
        for (int j = min(n, arr[i].dead) - 1; j >= 0; j--)
        {
            // Free slot found
            if (slot[j] == false)
            {
                result[j] = i;  // Add this job to result
                slot[j] = true; // Make this slot occupied
                break;
            }
        }
    }

    // Print the result
    for (int i = 0; i < n; i++)
        if (slot[i])
            cout << arr[result[i]].id << " ";
}

// -----------------------END Job Scheduling

// Bin Packing Next Fit
int nextFit(int weight[], int n, int c)
{
    int res = 0, bin_rem = c;

    for (int i = 0; i < n; i++)
    {

        if (weight[i] > bin_rem)
        {
            res++;
            bin_rem = c - weight[i];
        }
        else
            bin_rem -= weight[i];
    }
    return res;
}

// Bin Packing First Fit
int firstFit(int weight[], int n, int c)
{
    int res = 0;

    int bin_rem[n];

    for (int i = 0; i < n; i++)
    {
        int j;
        for (j = 0; j < res; j++)
        {
            if (bin_rem[j] >= weight[i])
            {
                bin_rem[j] = bin_rem[j] - weight[i];
                break;
            }
        }

        if (j == res)
        {
            bin_rem[res] = c - weight[i];
            res++;
        }
    }
    return res;
}

// Bin Packing Best Fit
int bestFit(int weight[], int n, int c)
{
    int res = 0;

    int bin_rem[n];

    for (int i = 0; i < n; i++)
    {
        int j;

        int min = c + 1, bi = 0;

        for (j = 0; j < res; j++)
        {
            if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] < min)
            {
                bi = j;
                min = bin_rem[j] - weight[i];
            }
        }

        if (min == c + 1)
        {
            bin_rem[res] = c - weight[i];
            res++;
        }
        else
            bin_rem[bi] -= weight[i];
    }
    return res;
}

// =====================================================================================================================//
// =====================================================================================================================//

bool validParentheses(string st)
{
    stack<char> s;
    for (char c : st)
    {
        if (c == '(')
            s.push(')');
        else if (c == '{')
            s.push('}');
        else if (c == '[')
            s.push(']');
        else if (s.empty())
            return false;
        else
        {
            char t = s.top();
            s.pop();
            if (t != c)
                return false;
        }
    }
    return s.empty();
}

void nextGreatest(vector<int> nums)
{
    stack<int> s;
    vector<int> ans(nums.size(), -1);
    int i = 0;
    while (i < nums.size())
    {
        if (s.empty() || (nums[i] <= nums[s.top()]))
        {
            s.push(i++);
        }
        else
        {
            int top = s.top();
            s.pop();
            ans[top] = nums[i];
        }
    }
    for (auto a : ans)
        cout << a << " ";
}

// =====================================================================================================================//
// =====================================================================================================================//

class Node
{
public:
    int val;
    Node *next = NULL;
    Node *prev = NULL;
    Node(int data)
    {
        this->val = data;
    }
};

class DoublyLinkedList
{
public:
    Node *head = NULL;
    Node *rear = NULL;
    Node *middle = NULL;
    int size = 0;

    void push_back(int data)
    {
        if (head == NULL)
        {
            head = new Node(data);
            rear = head;
            middle = head;
            size++;
            return;
        }
        rear->next = new Node(data);
        rear->next->prev = rear;
        rear = rear->next;
        if (size % 2 == 0)
            middle = middle->next;
        size++;
    }

    void push_front(int data)
    {
        if (head == NULL)
        {
            head = new Node(data);
            rear = head;
            middle = head;
            size++;
            return;
        }
        head->prev = new Node(data);
        head->prev->next = head;
        head = head->prev;
        if (size % 2 == 1)
            middle = middle->prev;
        size++;
    }

    void pop_front()
    {
        if (head == NULL)
            return;
        if (head == rear)
        {
            head = NULL;
            rear = NULL;
            middle = NULL;
            size--;
            return;
        }

        head = head->next;
        head->prev = NULL;
        if (size % 2 == 0)
            middle = middle->next;
        size--;
    }

    void pop_back()
    {
        if (head == NULL)
            return;
        if (head == rear)
        {
            head = NULL;
            rear = NULL;
            middle = NULL;
            size--;
            return;
        }
        rear = rear->prev;
        rear->next = NULL;
        if (size % 2 == 1)
            middle = middle->prev;
        size--;
    }

    void get_last()
    {
        if (rear != NULL)
            cout << rear->val;
        else
            cout << -1;

        cout << "\n";
    }

    void get_first()
    {
        if (head != NULL)
            cout << head->val;
        else
            cout << -1;

        cout << "\n";
    }

    void insert_after(Node *pos, int value)
    {
        if (pos == nullptr)
            return;
        Node *newnode = new Node(value);
        newnode->prev = pos;
        newnode->next = pos->next;
        if (pos->next != nullptr)
            pos->next->prev = newnode;
        pos->next = newnode;
        size++;
    }

    void insert_before(Node *pos, int value)
    {
        if (pos == nullptr)
            return;
        Node *newnode = new Node(value);
        newnode->next = pos;
        newnode->prev = pos->prev;
        if (pos->prev != nullptr)
            pos->prev->next = newnode;
        pos->prev = newnode;
        size++;
    }

    void printList()
    {
        Node *temp = this->head;
        while (temp != NULL)
        {
            cout << temp->val << " ";
            temp = temp->next;
        }
        cout << "\n";
    }

    void find_middle()
    {
        cout << this->middle->val << "\n";
    }

    bool empty()
    {
        return this->size == 0;
    }

    Node *search(int index)
    {

        Node *retv = head;
        for (int t = 0; t < index && retv != nullptr; t++)
        {
            retv = retv->next;
        }
        return retv;
    }

    void reverse()
    {
        Node *temp = NULL;
        Node *current = head;

        while (current != NULL)
        {
            temp = current->prev;
            current->prev = current->next;
            current->next = temp;
            current = current->prev;
        }

        /* Before changing the head, check for the cases like empty  
            list and list with only one node */
        if (temp != NULL)
            head = temp->prev;
    }
};

class Stck
{
public:
    DoublyLinkedList s;
    void push(int data)
    {
        s.push_back(data);
    }
    void pop()
    {
        s.pop_back();
    }
    int top()
    {
        if (s.rear)
            return s.rear->val;
        else
            return -1;
    }

    int midval()
    {
        if (s.middle)
            return s.middle->val;
        else
            return -1;
    }
};

class Que
{
public:
    DoublyLinkedList s;

    void push(int data)
    {
        s.push_back(data);
    }
    void pop()
    {
        s.pop_front();
    }
    int front()
    {
        if (s.head)
            return s.head->val;
        else
            return -1;
    }

    int midval()
    {
        if (s.middle)
            return s.middle->val;
        else
            return -1;
    }
};

// Queue using stack
class MyQueue
{
public:
    stack<int> s1;
    MyQueue()
    {
    }

    void push(int x)
    {
        if (s1.empty())
        {
            s1.push(x);
            return;
        }
        stack<int> s2;
        while (!s1.empty())
        {
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);
        while (!s2.empty())
        {
            s1.push(s2.top());
            s2.pop();
        }
    }

    int pop()
    {
        int x = s1.top();
        s1.pop();
        return x;
    }

    int peek()
    {
        return s1.top();
    }

    bool empty()
    {
        return s1.empty();
    }
};

// Stack using queue
class MyStack
{
public:
    queue<int> q1;
    MyStack()
    {
    }

    void push(int x)
    {
        if (q1.empty())
        {
            q1.push(x);
            return;
        }
        queue<int> q2;
        while (!q1.empty())
        {
            q2.push(q1.front());
            q1.pop();
        }
        q1.push(x);
        while (!q2.empty())
        {
            q1.push(q2.front());
            q2.pop();
        }
    }

    int pop()
    {
        int f = q1.front();
        q1.pop();
        return f;
    }

    int top()
    {
        return q1.front();
    }

    bool empty()
    {
        return q1.empty();
    }
};

// ************** Singly Linked List *************
struct Node
{
    int data;
    struct Node *next;
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};

struct LinkedList
{
    Node *head;
    LinkedList()
    {
        head = NULL;
    }

    /* Function to reverse the linked list */
    void reverse()
    {
        // Initialize current, previous and
        // next pointers
        Node *current = head;
        Node *prev = NULL, *next = NULL;

        while (current != NULL)
        {
            // Store next
            next = current->next;

            // Reverse current node's pointer
            current->next = prev;

            // Move pointers one position ahead.
            prev = current;
            current = next;
        }
        head = prev;
    }

    /* Function to print linked list */
    void print()
    {
        struct Node *temp = head;
        while (temp != NULL)
        {
            cout << temp->data << " ";
            temp = temp->next;
        }
    }

    void push(int data)
    {
        Node *temp = new Node(data);
        temp->next = head;
        head = temp;
    }
};

int main()
{

    return 0;
}