GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
public:
    vector<int> FindExitPoint(int n, int m, vector<vector<int>>& matrix) {
        int i = 0,  j = 0, dir = 0;
        
        while(i < n and j < m and i >= 0 and j >= 0) {
            if(matrix[i][j] == 1) {
                matrix[i][j] = 0;
                dir++;
            }
            
            dir %= 4;
            switch(dir) {
                case 0: j++; 
                        break;
                
                case 1: i++;
                        break;
                
                case 2: j--;
                        break;
                
                case 3: i--;
                        break;
            }
        }
        
        switch(dir) {
            case 1: return {i - 1, j};
            case 2: return {i, j + 1};
            case 3: return {i + 1, j};
        }
        
        return {i, j - 1};
    }
};

class Solution {
  public:
    int findMaxSum(int n, int m, vector<vector<int>> mat) {
        int ans=-1;
        for(int i=1;i<n-1;i++){
            
            for(int j=1;j<m-1;j++){
                
                int sum=mat[i][j]+mat[i-1][j]+mat[i+1][j]+mat[i-1][j-1]+mat[i+1][j+1]+mat[i-1][j+1]+mat[i+1][j-1];
                ans=max(ans,sum);
            }
        }
        return ans;
    }
};

class Solution{
public:
    const int MOD = 1e9 + 7;
    int ways(int x, int y)
    {
        x++; y++;
        vector<vector<int>> dp(x, vector<int> (y, 0));
        for(int i = 0 ; i < x ; i++) {
            dp[i][0] = 1;
        }
        for(int j = 0 ; j < y ; j++) {
            dp[0][j] = 1;
        }
        for(int i = 1 ; i < x ; i++) {
            for(int j = 1 ; j < y ; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            }
        }
        return dp[x - 1][y - 1];
    }
};

class Solution {
  public:
  int mod=1e9+7;
    int firstElement(int n) {
        int a10=1,a11=0;
        for(int i=0;i<n-1;i++){
            int temp=a10+a11;
            a11=a10;
            a10=temp%mod;
        } 
        return a10;
    }
};

class Solution {
  public:
    int minRow(int n, int m, vector<vector<int>> a) {
     
        int mini=INT_MAX;
        int cnt=0;
        int ans=0;
        
        for(int i=0;i<n;i++)
        {
            cnt=0;
            for(int j=0;j<m;j++)
            {
                if(a[i][j]) cnt++;
            }
            ans=cnt<mini?i:ans;
            mini=min(mini,cnt);
        }
        return ans+1;
    }
};

class Solution{   
public:
    void threeWayPartition(vector<int>& array,int a, int b)
    {   
        int n=array.size();
        int j=0;
        int k=n-1;
        for(int i=0;i<n;i++){
            if(array[i]<a) {
                swap(array[i],array[j]);
                j++;
            }
        }
        for(int i=n-1;i>=0;i--){
            if(array[i]>b){
                swap(array[i],array[k]);
                k--;
            }
        }
    }
};

class Solution{   
public:
    void threeWayPartition(vector<int>& array,int a, int b)
    {   
        int n=array.size();
        int j=0;
        int k=n-1;
        for(int i=0;i<n;i++){
            if(array[i]<a) {
                swap(array[i],array[j]);
                j++;
            }
        }
        for(int i=n-1;i>=0;i--){
            if(array[i]>b){
                swap(array[i],array[k]);
                k--;
            }
        }
    }
};

class Solution{
    public:
    //arr1,arr2 : the arrays
    // n, m: size of arrays
    //Function to return a list containing the union of the two arrays. 
    vector<int> findUnion(int arr1[], int arr2[], int n, int m)
    {
        set <int>  s ;
        for(int i = 0 ; i < n ; i++) {
            s.insert(arr1[i])  ;
        }
        
        for(int j = 0 ; j < m ; j++) {
            s.insert(arr2[j])  ;
        }
        vector <int> ans ;
        for( auto it : s) {
            ans.push_back(it) ;
        }
        
        return ans ;
    }
};

class Solution{
 
 public:
 vector<int> findMissing(int a[], int b[], int n, int m) 
 { 
     vector<int>ans;
     int i=0;
     unordered_map<int,bool>mp;
     for(i;i<m;i++){
         mp[b[i]] = true;
     }
     for(i=0;i,i<n;i++){
         if(!mp[a[i]])ans.push_back(a[i]);
     }
     return ans;
 }
};

class Solution {
  public:
  vector<int> twoRepeated (int arr[], int n) {
        vector<int> ans;
        for(int i=0; i<n+2; i++){
            int ind = abs(arr[i]);
            if(arr[ind]>0){
                arr[ind] = -arr[ind];
            }
            else{
                ans.push_back(ind);
            }
        }
        return ans;
  }
};

class Solution{
    public:
    int countPairs(int arr[] , int n ) 
    {
        vector<int> b,s;
        for(int i=0;i<n;i++){
            b.push_back((i * arr[i]));
            s.push_back(b[i]);
        }
        sort(s.begin(), s.end());
        int ans = 0;
        for(int i=0; i<n; i++){
            int i1 = lower_bound(s.begin(), s.end(), b[i]) - s.begin();
            ans += i1;
            s.erase((s.begin() + i1));
        }
        return ans;
    }
};