#include <iostream>

using namespace std;

// Node structure for a linked list
struct Node {
    int data;
    Node* next;
    
    // Constructor
    Node(int value) : data(value), next(nullptr) {}
};

// Singly Linked List class
class SinglyLinkedList {
private:
    Node* head;

public:
    // Constructor
    SinglyLinkedList() : head(nullptr) {}

    // Function to insert an element at the beginning
    void insertAtBeginning(int value) {
        Node* newNode = new Node(value);
        newNode->next = head;
        head = newNode;
    }

    // Function to delete an element from the beginning
    void deleteFromBeginning() {
        if (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }

    // Function to insert an element at the end
    void insertAtEnd(int value) {
        Node* newNode = new Node(value);

        if (!head) {
            head = newNode;
            return;
        }

        Node* temp = head;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = newNode;
    }

    // Function to delete an element from the end
    void deleteFromEnd() {
        if (!head) {
            return;
        }

        if (!head->next) {
            delete head;
            head = nullptr;
            return;
        }

        Node* temp = head;
        while (temp->next->next) {
            temp = temp->next;
        }

        delete temp->next;
        temp->next = nullptr;
    }

    // Function to display the linked list
    void display() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

// Circular Linked List class (inherits from SinglyLinkedList)
class CircularLinkedList : public SinglyLinkedList {
public:
    // Function to insert an element at the end (overridden)
    void insertAtEnd(int value) override {
        Node* newNode = new Node(value);

        if (!head) {
            head = newNode;
            newNode->next = head;
            return;
        }

        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }

        temp->next = newNode;
        newNode->next = head;
    }

    // Function to delete an element from the end (overridden)
    void deleteFromEnd() override {
        if (!head) {
            return;
        }

        if (head->next == head) {
            delete head;
            head = nullptr;
            return;
        }

        Node* temp = head;
        Node* prev = nullptr;
        while (temp->next != head) {
            prev = temp;
            temp = temp->next;
        }

        prev->next = head;
        delete temp;
    }
};

int main() {
    // Singly Linked List example
    SinglyLinkedList sll;
    sll.insertAtBeginning(3);
    sll.insertAtBeginning(2);
    sll.insertAtBeginning(1);
    sll.display();  // Output: 1 2 3
    sll.deleteFromBeginning();
    sll.display();  // Output: 2 3
    sll.insertAtEnd(4);
    sll.insertAtEnd(5);
    sll.display();  // Output: 2 3 4 5
    sll.deleteFromEnd();
    sll.display();  // Output: 2 3 4

    // Circular Linked List example
    CircularLinkedList cll;
    cll.insertAtEnd(1);
    cll.insertAtEnd(2);
    cll.insertAtEnd(3);
    cll.display();  // Output: 1 2 3
    cll.deleteFromEnd();
    cll.display();  // Output: 1 2
    cll.insertAtEnd(4);
    cll.insertAtEnd(5);
    cll.display();  // Output: 1 2 4 5

    return 0;
}

#include <iostream>
using namespace std;

const int MAX_SIZE = 100; // Maximum size of the stack

class StaticStack {
private:
    int arr[MAX_SIZE];
    int top;

public:
    // Constructor to initialize the stack
    StaticStack() {
        top = -1; // Initialize top to -1 indicating an empty stack
    }

    // Function to push an element onto the stack
    void push(int value) {
        if (top == MAX_SIZE - 1) {
            cout << "Stack is full. Cannot push." << endl;
            return;
        }
        arr[++top] = value;
        cout << value << " pushed onto the stack." << endl;
    }

    // Function to pop an element from the stack
    void pop() {
        if (isEmpty()) {
            cout << "Stack is empty. Cannot pop." << endl;
            return;
        }
        cout << arr[top--] << " popped from the stack." << endl;
    }

    // Function to check if the stack is empty
    bool isEmpty() {
        return top == -1;
    }

    // Function to check if the stack is full
    bool isFull() {
        return top == MAX_SIZE - 1;
    }
};

int main() {
    // Example usage
    StaticStack stack;

    cout << "Is the stack empty? " << (stack.isEmpty() ? "Yes" : "No") << endl;

    stack.push(5);
    stack.push(10);
    stack.push(15);

    cout << "Is the stack full? " << (stack.isFull() ? "Yes" : "No") << endl;

    stack.pop();
    stack.pop();
    stack.pop();
    stack.pop(); // Trying to pop from an empty stack

    return 0;
}
#include <iostream>
using namespace std;

// Function to calculate power in O(log(n)) time
double power(double x, int n) {
    if (n == 0) {
        return 1;
    }

    double temp = power(x, n / 2);
    if (n % 2 == 0) {
        return temp * temp;
    } else {
        if (n > 0) {
            return x * temp * temp;
        } else {
            return (temp * temp) / x;
        }
    }
}

int main() {
    // Example usage
    double base = 2;
    int exponent = 5;

    double result = power(base, exponent);

    cout << base << " raised to the power " << exponent << " is: " << result << endl;

    return 0;
}
#include <iostream>
#include <vector>

using namespace std;

// Function to partition the array and return the pivot index
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// Function to perform the Quicksort algorithm
void quicksort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);

        // Recursively sort the subarrays
        quicksort(arr, low, pivotIndex - 1);
        quicksort(arr, pivotIndex + 1, high);
    }
}

int main() {
    // Example usage
    vector<int> array = {12, 7, 11, 5, 6, 2, 8};

    cout << "Original array: ";
    for (int num : array) {
        cout << num << " ";
    }
    cout << endl;

    int size = array.size();
    quicksort(array, 0, size - 1);

    cout << "Sorted array: ";
    for (int num : array) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}