GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
public:   
    int minValue(Node* root) {
        
         if(!root){
            return 1e9;
        }
        return min( root->data,min( minValue(root->left), minValue(root->right) ) ) ;
    }
};

class Solution {
public:
 bool isEularCircuitExist(int v, vector<int>adj[]){
     
     for(int i = 0; i < v; i++){
         if(adj[i].size() % 2 != 0){
             return 0;
         }
     }
     return 1;
 }
};

class Solution { public: bool isEularCircuitExist(int v, vector<int>adj[]){ for(int i = 0; i < v; i++){ if(adj[i].size() % 2 != 0){ return 0; } } return 1; } };

class Solution {
  public:
    int findCity(int n, int m, vector<vector<int>>& edges,int distanceThreshold)
    { 
        
       vector<vector<int>> mat(n,vector<int>(n,1e9));
       for(auto it:edges)
       {
           mat[it[0]][it[1]]=it[2];
           mat[it[1]][it[0]]=it[2];
       }
       for(int i=0;i<n;i++)
       {
           mat[i][i]=0;
       }
       for(int k=0;k<n;k++)
       {
           for(int i=0;i<n;i++)
           {
               for(int j=0;j<n;j++)
               {
                   mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
               }
           }
       }
       int ans;
       int mini=1e9;
       for(int i=0;i<n;i++)
       {
            int reach=0;
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]<=distanceThreshold)
                {
                       reach++;
                }
            }
            if(reach<=mini)
            {
                mini=reach;
                ans=i;
               }
        }
           
        return ans;
    }
};

class Solution{
public:
    int findShortestPath(vector<vector<int>> &mat)
    {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int>> vis(n, vector<int>(m));
        int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mat[i][j] == 0)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 and ny >= 0 and nx < n and ny < m and mat[nx][ny] == 1)
                            mat[nx][ny] = -1;
                    }
                }
            }
        }

        queue<pair<int, pair<int, int>>> q;
        for (int i = 0; i < n; i++)
        {
            if (mat[i][0] == 1)
            {
                q.push({0, {i, 0}});
                vis[i][0] = 1;
            }
        }

        int ans = INT_MAX;
        while (!q.empty())
        {
            int dist = q.front().first;
            int r = q.front().second.first;
            int c = q.front().second.second;
            q.pop();

            if (c == m - 1)
                ans = min(ans, dist + 1);

            for (int k = 0; k < 4; k++)
            {
                int nx = r + dx[k];
                int ny = c + dy[k];

                if (nx >= 0 and ny >= 0 and nx < n and ny < m and mat[nx][ny] == 1 and !vis[nx][ny])
                {
                    vis[nx][ny] = 1;
                    q.push({dist + 1, {nx, ny}});
                }
            }
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

class Solution
{
public:
    bool isAdditiveSequence(string s)
    {
        int n = s.size();
        int num1 = 0;
        for (int i = 0; i < n / 2; i++)
        {
            num1 = num1 * 10 + (s[i] - '0');
            int num2 = 0;
            for (int j = i + 1; j < n - 1; j++)
            {
                num2 = num2 * 10 + (s[j] - '0');
                int prev2 = num1, prev1 = num2;
                int num = 0;
                int k = j + 1;
                while (k < n)
                {
                    num = num * 10 + (s[k] - '0');
                    if (num == (prev1 + prev2))
                    {
                        prev2 = prev1;
                        prev1 = num;
                        num = 0;
                    }
                    k++;
                }
                if (k == n && num == 0)
                    return 1;
            }
        }
        return 0;
    }
};

class Solution{
public:
 
    bool isValid(string output){
        int i = 0;
        int ones = 0 , zeros = 0;
        while(i < output.size()){
            if(output[i] == '1'){
                ones++;
            }
            else{
                zeros++;
            }
            
            if(ones < zeros){
                return false;
            }
            i++;
        }
        return true;
    }
 
    void solve(int n , string output , vector<string> &ans){
        if(n == 0){
            if(isValid(output)){
                ans.push_back(output);
            }
            return;
        }
        
        solve(n-1,output+"1",ans);
        solve(n-1,output+"0",ans);
    }
 
vector<string> NBitBinary(int n)
{
    vector<string> ans;
    string output = "";
    solve(n,output,ans);
    return ans;
}
};

class Solution{
public:
    void insert(stack<int>&st,int x){
        if(st.empty()){
            st.push(x);
            return;
        }
        int t = st.top();
        st.pop();
        insert(st,x);
        st.push(t);
        return;
    }
    stack<int> insertAtBottom(stack<int> st,int x){
        insert(st,x);
        return st;
    }
};

class Solution {
  public:
    vector<int> Series(int n) {
        
         if(n==0)
         return {0};
          if(n==1)
         return {0,1};
         vector<int>ans(n+1);//Create a vector to store Fibonacci series take( n+1) because start with 0;
         int mod=1e9+7; // create module function
         ans[0]=0; // first / First Fibonacci numb
         ans[1]=1;//// Second Fibonacci number
         for(int i=2;i<=n;i++)
         {
             ans[i]=(ans[i-1]+ans[i-2])%mod; //Calculate Fibonacci number and take modulo
             
         }
         return ans;
        
    }
};