GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
  public:
  void solve(int &maxi,Node* root){
      
      if(root==NULL)
      return;
      maxi=max(maxi,root->data);
      solve(maxi,root->left);
      solve(maxi,root->right);
      
  }
  void constructGraph(Node* root,vector<int>adj[]){
      
      if(root==NULL)
      return;
      if(root->left){
          adj[root->data].push_back(root->left->data);
          adj[root->left->data].push_back(root->data);
      }
      if(root->right){
          adj[root->data].push_back(root->right->data);
          adj[root->right->data].push_back(root->data);
      }
      constructGraph(root->left,adj);
      constructGraph(root->right,adj);
  }
    int minTime(Node* root, int target) 
    {
        int maxi=-1;
        solve(maxi,root);
        vector<int>adj[maxi+1];
        constructGraph(root,adj);
        queue<pair<int,int>>q;
        vector<bool>visit(maxi+1,false);
        q.push({0,target});
        visit[target]=true;
        int ans=0;
        while(q.empty()==false){
            int dist=q.front().first;
            int u=q.front().second;
            q.pop();
            ans=max(ans,dist);
            for(auto v:adj[u]){
                if(visit[v]==false){
                    visit[v]=true;
                    q.push({dist+1,v});
                }
            }
        }
        return ans;
    }
};

class Solution {
  public:
    int kthSmallest(vector<int> &arr, int k) {
        int maxi=*max_element(arr.begin(),arr.end());
        vector<int>freq(maxi+1,0);
        for(int i=0;i<arr.size();i++)
        freq[arr[i]]++;
        for(int i=0;i<=maxi;i++){
            if(freq[i]!=0){
                k--;
                if(k==0)
                return i;
            }
        }
        return -1;
    }
};

class Solution {
  public:
    bool canSplit(vector<int>& arr) {
        long long sum1=0;
        long long sum2=0;
        for(auto x:arr)
        sum1+=x;
        for(int i=arr.size()-1;i>=0;i--){
            
            sum2+=arr[i];
            sum1-=arr[i];
            if(sum2==sum1)
            return true;
        }
        return false;
    }
};

class Solution {
  public:
    
    vector<long long int> productExceptSelf(vector<long long int>& nums) {

        vector<long long int>ans;
         long long  n=1;
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<nums.size(); j++){
                if(j!=i)
                n=n*nums[j];
            }
             ans.push_back(n);
             n=1;
        }
        return ans;
    }
};

class Solution
{
    public:
    
    int maximizeTheCuts(int n, int x, int y, int z)
    {
        
        vector<int> dp(n + 1, INT_MIN);
        
        dp[0] = 0;
        for(int i = 1; i <= n; ++i){
            if(i - x >= 0){
                
                dp[i] = max(dp[i - x] == INT_MIN ? INT_MIN : dp[i - x] + 1, dp[i]);
            }
            if(i - y >= 0){
                dp[i] = max(dp[i - y] == INT_MIN ? INT_MIN : dp[i - y] + 1, dp[i]);
            }
            if(i - z >= 0){
                dp[i] = max(dp[i - z] == INT_MIN ? INT_MIN : dp[i - z] + 1, dp[i]);
            }
        }
        return dp[n] == INT_MIN ? 0 : dp[n];
    }
};

class Solution {
  public:
    Node* addOne(Node* head) {
        Node* temp = head;
        Node* change = NULL;
        while(temp){
            Node* prev = temp;
            if(temp->next == NULL){
                if(temp->data < 9){
                    temp->data += 1;
                    return head;
                }
                break;
            }
            temp = temp->next;
            if(prev->data!=9 && temp && temp->data==9){
                change = prev;
            }
        }
        if(change==NULL){
            Node* first = new Node(1);
            first->next = head;
            while(head){
                head->data = 0;
                head= head->next;
            }
            return first;
        }
        else{
            change->data += 1;
            change = change->next;
            while(change){
                change->data = 0;
                change= change->next;
            }
            return head;
        }
        return head;
    }
};

class Solution {
public:
    int longestCommonSubstr(string str1, string str2) {
        int n = str1.length();
        int m = str2.length();
        vector<vector<int>> dp(2, vector<int>(m + 1, 0));
        int maxLength = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
                    maxLength = max(maxLength, dp[i % 2][j]);
                } else {
                    dp[i % 2][j] = 0;
                }
            }
        }
        
        return maxLength;
    }
};

class Solution {
  public:
    long long int floorSqrt(long long int n) {
        return sqrtl(n);
    }
};

class Solution {
  public:
    int SumofMiddleElements(vector<int> &arr1, vector<int> &arr2) {
        vector<int> sol;
        
        int idx1 = 0;
        int idx2 = 0;
        int n1 = arr1.size(), n2 = arr2.size();
        
        while(idx1 < n1 && idx2 < n2){
            if(arr1[idx1] <= arr2[idx2])
                sol.push_back(arr1[idx1++]);
            else
                sol.push_back(arr2[idx2++]);
        }
        
        while(idx1 < n1) sol.push_back(arr1[idx1++]);
        while(idx2 < n2) sol.push_back(arr2[idx2++]);
        
        int size = n1 + n2;
        
        if(size % 2 == 0)
            return sol[size/2] + sol[size/2 - 1];
        
        return sol[size/2];
        
    }
};