Matrix · Intermediate DSA
Advanced OOP & Memory

int matrixSum(vector<vector<int>>& m){
    int sum=0;
    for(auto& row : m)
        for(int x : row) sum += x;
    return sum;
}

int diagonalSum(vector<vector<int>>& m){
    int n=m.size(), sum=0;
    for(int i=0; i<n; i++){
        sum += m[i][i];            // primary
        sum += m[i][n-1-i];       // secondary
    }
    if(n%2) sum -= m[n/2][n/2];  // centre counted twice for odd n
    return sum;
}

int diagDiff(vector<vector<int>>& m){
    int n=m.size(), p=0, s=0;
    for(int i=0; i<n; i++){ p += m[i][i]; s += m[i][n-1-i]; }
    return abs(p-s);
}

bool identical(vector<vector<int>>& A,
               vector<vector<int>>& B){
    if(A.size()!=B.size() || A[0].size()!=B[0].size())
        return false;
    return A==B;  // vector == does element-wise comparison
}

bool isToeplitz(vector<vector<int>>& m){
    int R=m.size(), C=m[0].size();
    for(int i=1; i<R; i++)
        for(int j=1; j<C; j++)
            if(m[i][j] != m[i-1][j-1]) return false;
    return true;
}

long long numDiagonals(int n){
    return (long long)n * (n-3) / 2;
}
// Guard: n must be >= 3 (a polygon has at least 3 vertices)

bool isAutomorphic(int n){
    long long sq = (long long)n * n;
    int digits = to_string(n).size();
    long long mod = 1;
    for(int i=0; i<digits; i++) mod *= 10; // 10^digits (avoid pow)
    return sq % mod == n;
}

bool isPowerOf(int a, int b){
    if(b < 2 || a <= 0) return false;
    while(a % b == 0) a /= b;
    return a == 1;    // a == 1 means fully divided away
}
// isPowerOf(1, any) = true  (b^0 = 1)
// isPowerOf(27,3) = true    (3^3)

pair<int,int> nearestPow2(int n){
    if(n <= 0) return {0, 1};
    int lo = 1 << (int)log2(n);  // largest power of 2 <= n
    int hi = (lo == n) ? lo : lo << 1;  // smallest power of 2 >= n
    return {lo, hi};
}
// n=13 → {8, 16}  |  n=16 → {16, 16}

void oddTriangle(int n){
    int num = 1;
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++){
            cout << num << " ";
            num += 2;          // advance to next odd number
        }
        cout << "\n";
    }
}

int floorSqrt(int n){
    if(n < 2) return n;
    long long lo=1, hi=n, ans=1;
    while(lo <= hi){
        long long mid = lo + (hi-lo)/2;
        if(mid*mid == n) return (int)mid;
        if(mid*mid < n){ ans=mid; lo=mid+1; }
        else            hi=mid-1;
    }
    return (int)ans;
}

bool isArmstrong(int n){
    string s = to_string(n);
    int d = s.size(), sum = 0;
    for(char c : s){
        int digit = c - '0';
        int pw = 1;
        for(int i=0; i<d; i++) pw *= digit; // integer pow, no float
        sum += pw;
    }
    return sum == n;
}
void armstrongRange(int L, int R){
    for(int i=L; i<=R; i++)
        if(isArmstrong(i)) cout << i << " ";
    cout << "\n";
}
// 3-digit: 153, 370, 371, 407  |  4-digit: 1634, 8208, 9474

int nthRoot(int n, int k){
    long long lo=1, hi=n;
    while(lo <= hi){
        long long mid = lo + (hi-lo)/2;
        long long pw = 1;
        for(int i=0; i<k; i++){
            pw *= mid;
            if(pw > n){ pw = n+1; break; } // overflow guard
        }
        if(pw == n) return (int)mid;
        if(pw < n) lo = mid+1;
        else       hi = mid-1;
    }
    return -1;  // not a perfect k-th power
}

int minSteps(int n){
    vector<int> dp(n+1, INT_MAX);
    dp[1] = 0;
    for(int i=2; i<=n; i++){
        dp[i] = dp[i-1] + 1;                       // subtract 1
        if(i%2==0) dp[i] = min(dp[i], dp[i/2]+1);  // divide by 2
        if(i%3==0) dp[i] = min(dp[i], dp[i/3]+1);  // divide by 3
    }
    return dp[n];
}
// n=1→0, n=2→1, n=3→1, n=10→3, n=15→4

string toRoman(int n){
    vector<pair<int,string>> vals = {
        {1000,"M"}, {900,"CM"}, {500,"D"}, {400,"CD"},
        { 100,"C"}, { 90,"XC"}, { 50,"L"}, { 40,"XL"},
        {  10,"X"}, {  9,"IX"}, {  5,"V"}, {  4,"IV"},
        {   1,"I"}
    };
    string res;
    for(auto& [v, s] : vals)
        while(n >= v){ res += s; n -= v; }
    return res;
}

void rotate90(vector<vector<int>>& m){
    int n = m.size();
    // Step 1: Transpose (swap across main diagonal)
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            swap(m[i][j], m[j][i]);
    // Step 2: Reverse each row
    for(int i=0; i<n; i++)
        reverse(m[i].begin(), m[i].end());
}

int majorityElement(vector<int>& a){
    int cand = a[0], cnt = 1;
    for(int i=1; i<(int)a.size(); i++){
        if     (cnt == 0)    { cand = a[i]; cnt = 1; }
        else if(a[i] == cand)  cnt++;
        else                    cnt--;
    }
    return cand;   // guaranteed to exist, no verification needed
}

int longestSubarraySum(vector<int>& a, int k){
    unordered_map<long long, int> first;
    first[0] = -1;         // prefix sum 0 exists before index 0
    long long psum = 0;
    int maxLen = 0;
    for(int i=0; i<(int)a.size(); i++){
        psum += a[i];
        if(first.count(psum - k))
            maxLen = max(maxLen, i - first[psum - k]);
        if(!first.count(psum))   // store FIRST occurrence only
            first[psum] = i;
    }
    return maxLen;
}

int trapRainWater(vector<int>& h){
    int l=0, r=(int)h.size()-1;
    int maxL=0, maxR=0, water=0;
    while(l < r){
        if(h[l] <= h[r]){
            if(h[l] >= maxL) maxL = h[l];
            else             water += maxL - h[l];
            l++;
        } else {
            if(h[r] >= maxR) maxR = h[r];
            else             water += maxR - h[r];
            r--;
        }
    }
    return water;
}

class StringBox {
    char* data;
public:
    // Constructor
    StringBox(const char* str){
        data = new char[strlen(str)+1];
        strcpy(data, str);
    }
    // Destructor
    ~StringBox(){ delete[] data; }

    // Copy Constructor (deep)
    StringBox(const StringBox& o){
        data = new char[strlen(o.data)+1];
        strcpy(data, o.data);
    }

    // Copy Assignment Operator (deep)
    StringBox& operator=(const StringBox& o){
        if(this == &o) return *this;  // self-assignment guard
        delete[] data;
        data = new char[strlen(o.data)+1];
        strcpy(data, o.data);
        return *this;
    }
};

class Buffer {
    int* arr; int size;
public:
    Buffer(int s) : size(s), arr(new int[s]) {}
    ~Buffer(){ delete[] arr; }

    // Copy Constructor (deep)
    Buffer(const Buffer& o) : size(o.size), arr(new int[o.size]){
        for(int i=0;i<size;i++) arr[i]=o.arr[i];
    }

    // Move Constructor — steal the pointer
    Buffer(Buffer&& o) noexcept : arr(o.arr), size(o.size){
        o.arr  = nullptr;  // neutralize source
        o.size = 0;
    }

    // Move Assignment Operator
    Buffer& operator=(Buffer&& o) noexcept{
        if(this != &o){
            delete[] arr;     // free current resource
            arr = o.arr;      size = o.size;
            o.arr = nullptr;  o.size = 0;
        }
        return *this;
    }
    // Mark copy/move assignment explicitly
    Buffer& operator=(const Buffer&) = delete;
};

class Device {
public:
    int voltage;
    Device(int v) : voltage(v) {}
    void powerOn(){ cout << "On at " << voltage << "V\n"; }
};

class Printer : virtual public Device {
public: Printer() : Device(110) {}
};
class Scanner : virtual public Device {
public: Scanner() : Device(220) {}
};
class Copier : public Printer, public Scanner {
public:
    // Most-derived class initialises virtual base directly
    Copier() : Device(110), Printer(), Scanner() {}
};

class Base {
public:
    Base(){ cout << "Base created\n"; }
    virtual ~Base(){ cout << "Base destroyed\n"; }
};

class Derived : public Base {
    int* data;
public:
    Derived(){ data = new int[1000]; cout << "Derived created\n"; }
    ~Derived() override{
        delete[] data;
        cout << "Derived destroyed\n";
    }
};

int main(){
    Base* p = new Derived();
    delete p;  // safe via virtual dispatch
}

struct Vector2D {
    float x, y;
    Vector2D(float x=0, float y=0) : x(x), y(y) {}

    // + returns a new vector
    Vector2D operator+(const Vector2D& o) const{
        return {x+o.x, y+o.y};
    }
    // * returns scalar dot product
    float operator*(const Vector2D& o) const{
        return x*o.x + y*o.y;
    }
    // << must be a friend: left operand is ostream
    friend ostream& operator<<(ostream& os, const Vector2D& v){
        os << "[" << v.x << ", " << v.y << "]";
        return os;  // return os for chaining
    }
};

class Multiplier {
    int factor;
public:
    Multiplier(int f) : factor(f) {}

    int operator()(int value) const{
        return value * factor;
    }
};

int main(){
    Multiplier times3(3);
    cout << times3(10) << "\n";   // 30
    cout << times3(20) << "\n";   // 60

    // Plug into STL algorithms just like a lambda
    vector<int> v = {1, 2, 3};
    transform(v.begin(), v.end(), v.begin(), Multiplier(5));
    // v is now {5, 10, 15}
}

template<typename T>
class ScopedPointer {
    T* ptr;
public:
    explicit ScopedPointer(T* p = nullptr) : ptr(p) {}
    ~ScopedPointer(){ delete ptr; }

    T&  operator*()  const { return *ptr;  }
    T*  operator->() const { return  ptr;  }

    // Disable copying — makes this pointer "unique"
    ScopedPointer(const ScopedPointer&)            = delete;
    ScopedPointer& operator=(const ScopedPointer&) = delete;
};

class BankVault {
    double totalCash = 1000000.0;
    int    vaultCode  = 90210;

    friend class Auditor;  // only Auditor bypasses encapsulation
public:
    void deposit(double amt){ totalCash += amt; }
};

class Auditor {
public:
    bool audit(const BankVault& v){
        cout << "Code: " << v.vaultCode << "\n"; // valid access
        return v.totalCash >= 500000.0;
    }
};

class QueryBuilder {
    string query;
public:
    QueryBuilder& select(string fields){
        query = "SELECT " + fields + " ";
        return *this;
    }
    QueryBuilder& from(string table){
        query += "FROM " + table + " ";
        return *this;
    }
    QueryBuilder& where(string cond){
        query += "WHERE " + cond + ";";
        return *this;
    }
    void print(){ cout << query << "\n"; }
};

class Entity {
    static int count;  // one copy for the whole class
public:
    Entity(){ count++; }
    ~Entity(){ count--; }
    static int getCount(){ return count; }
};

// MUST be defined (not just declared) outside the class:
int Entity::count = 0;

int main(){
    Entity e1;
    { Entity e2, e3; cout << Entity::getCount(); }  // 3
    cout << Entity::getCount();  // 1
}

class Vector {
    int size;
public:
    explicit Vector(int s) : size(s) {}
};

void draw(Vector v){ /* ... */ }

int main(){
    // Vector v = 5;    ERROR: implicit conversion forbidden
    Vector v(5);       // OK: direct construction
    // draw(5);         ERROR: no implicit conversion
    draw(Vector(5));   // OK: explicit
}

class AppConfig {
    AppConfig(){ cout << "Config init\n"; }  // private
public:
    AppConfig(const AppConfig&) = delete;
    AppConfig& operator=(const AppConfig&) = delete;

    static AppConfig& get(){
        static AppConfig instance;  // created once, thread-safe (C++11)
        return instance;
    }
    void load(){ cout << "Loading config...\n"; }
};

// Usage: AppConfig::get().load();

#include <new>

class Enemy {
    int hp;
public:
    Enemy(int h) : hp(h){ cout << "Spawned hp=" << hp << "\n"; }
    ~Enemy(){              cout << "Enemy destroyed\n"; }
    void attack(){ cout << "Attack! hp=" << hp << "\n"; }
};

int main(){
    // 1. Allocate raw byte pool — constructors NOT called
    char* pool = new char[sizeof(Enemy) * 10];

    // 2. Construct Enemy at pool slot 0 — no OS call
    Enemy* e = new(pool) Enemy(100);
    e->attack();

    // 3. Manually destroy — do NOT use delete e!
    e->~Enemy();

    // 4. Release the pool block itself
    delete[] pool;
}