GeeksForGeeks - POTD | GFG POTD Answer

#include <cmath>
#include <algorithm>

class Solution {
public:
    long long int InternalCount(long long int p[], long long int q[], long long int r[]) {
        // Calculate area using the shoelace formula
        long long int area2 = abs(p[0]*(q[1] - r[1]) + q[0]*(r[1] - p[1]) + r[0]*(p[1] - q[1]));

        // Function to calculate the gcd
        auto gcd = [](long long int a, long long int b) {
            while (b) {
                long long int t = b;
                b = a % b;
                a = t;
            }
            return a;
        };

        // Calculate the number of boundary points
        long long int b1 = gcd(abs(p[0] - q[0]), abs(p[1] - q[1]));
        long long int b2 = gcd(abs(q[0] - r[0]), abs(q[1] - r[1]));
        long long int b3 = gcd(abs(r[0] - p[0]), abs(r[1] - p[1]));
        long long int boundaryPoints = b1 + b2 + b3;

        // Applying Pick's theorem to find internal points
        long long int internalPoints = (area2 - boundaryPoints + 2) / 2;

        return internalPoints;
    }
};

class Solution {
  public:
    double maxVolume(double perimeter, double area) {
        
        double length = (perimeter - sqrt((perimeter*perimeter) - 24*area))/12;
        double height = perimeter/4-2*length;
        return length*length*height;
    }
};

class Solution {
  public:
    int rectanglesInCircle(int r) {
        int limit = 4*r*r;
        int numRects = 0;
        int tempRects = -1;
        int diff = -1;
        for(int l = 1; ; ++l) {
            diff = limit - l*l;
            if(diff <= 0) 
                break;
            tempRects = (int)pow(diff, 0.5);
            if(tempRects == 0)
                break;
            numRects += tempRects;
        }
        return numRects;
    }
};

class Solution {
  public:
    string doIntersect(int p1[], int q1[], int p2[], int q2[]) {

        double m1 = (double)(q1[1] - p1[1]) / (double)(q1[0] - p1[0]);
        double m2 = (double)(q2[1] - p2[1]) / (double)(q2[0] - p2[0]);

        if(m1 == m2){
            return "false";
        }

        bool chk211 = p2[1]-p1[1] - m1*(p2[0]-p1[0]) >0?true:false;
        bool chk212 = q2[1]-p1[1] - m1*(q2[0]-p1[0]) >0?true:false;
        bool chk121 = p1[1]-p2[1] - m2*(p1[0]-p2[0]) >0?true:false;
        bool chk122 = q1[1]-p2[1] - m2*(q1[0]-p2[0]) >0?true:false;

        if((chk211==true && chk212 == true) || (chk211==false && chk212 == false) || 
        (chk121 == true && chk122 == true) || (chk121 == false && chk122 == false)){

            return "false";
        }
        return "true";

    }
};

class Solution {
  public:
    vector<int> getPrimes(int n) {
        vector<bool> isPrime(n+2 , true);
        isPrime[0] = false;
        isPrime[1] = false;
        for(int i = 2 ; i<n ;i++){
            if(isPrime[i]){
                for(int j = 2 ; i*j<n ;j++){
                    isPrime[i*j]=false;
                }
            }
        }
        for(int i = 2 ; i<n; i++){
            if(isPrime[i] && isPrime[n-i]){
                return {i , n-i};
            }
        }
        return {-1,-1};
    }
};

class Solution {
public:
    long long getCount(int n) {
        if (n == 1) return 10;
        vector<vector<int>> adj = {
            {0, 8},     // 0
            {1, 2, 4},  // 1
            {2, 1, 3, 5}, // 2
            {3, 2, 6},  // 3
            {4, 1, 5, 7}, // 4
            {5, 2, 4, 6, 8}, // 5
            {6, 3, 5, 9}, // 6
            {7, 4, 8}, // 7
            {8, 5, 7, 9, 0}, // 8
            {9, 6, 8}  // 9
        };

        vector<vector<long long>> dp(n + 1, vector<long long>(10, 0));

       
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

        // Fill the dp table
        for (int len = 2; len <= n; len++) {
            for (int digit = 0; digit < 10; digit++) {
                dp[len][digit] = 0;
                for (int neighbor : adj[digit]) {
                    dp[len][digit] += dp[len - 1][neighbor];
                }
            }
        }

        long long totalCount = 0;
        for (int digit = 0; digit < 10; digit++) {
            totalCount += dp[n][digit];
        }

        return totalCount;
    }
};

class Solution {
  public:
    string armstrongNumber(int n) {
        
        int z = n;
        
        int a = z%10;
        z = z/10;
        int b = z%10;
        z = z /10;
        int c = z%10;
        
        int ans = a*a*a + b*b*b + c*c*c;
        if(ans==n){
            return "true";
        }
        else
        return "false";
    }
};

class Solution
{
    public:
    int mod=1e9+7;
    int padovanSequence(int n)
    {
       vector<int> p(n+1,1);
       for(int i=3;i<=n;i++){
           p[i]=(p[i-2]+p[i-3])%mod;
       }
       return p[n];
    }
    
};

class Solution {
  public:
    int countNumberswith4(int n) {
        
         int count=0;
        for(int i=0;i<=n;i++){
            if(to_string(i).find("4")!=-1){
                count++;
            }
        }
        return count;
    }
};

class Solution {
  public:
    long long maxTip(int n, int x, int y, vector<int> &arr, vector<int> &brr) {
        vector<std::tuple<int, int, int>> orders; // (difference, tipA, tipB)
        for (int i = 0; i < n; ++i) {
            orders.emplace_back(std::abs(arr[i] - brr[i]), arr[i], brr[i]);
        }

        // Sort orders based on the absolute difference in descending order
        sort(orders.rbegin(), orders.rend());

        long long totalTips = 0;
        int countA = 0, countB = 0;

        // Distribute orders to maximize tips
        for (const auto& order : orders) {
            int diff = std::get<0>(order);
            int tipA = std::get<1>(order);
            int tipB = std::get<2>(order);

            if ((tipA >= tipB && countA < x) || countB >= y) {
                totalTips += tipA;
                countA++;
            } else {
                totalTips += tipB;
                countB++;
            }
        }

        return totalTips;
    }
};