GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
  public:
    int count_no_of_subset(vector<int> &arr, int sum1, vector<vector<long long int>> &t){
        for(int i=0;i<arr.size()+1;i++){
            for(int j=0;j<sum1+1;j++){
                if(i==0) t[i][j]=0;
                if(j==0) t[i][j]=1;
            }
        }
        long long int mod=1e9+7;
        
        for(int i=1;i<arr.size()+1;i++){
            for(int j=0;j<sum1+1;j++){
                if(arr[i-1]<=j){
                    t[i][j]=((t[i-1][j])+(t[i-1][j-arr[i-1]]))%mod;
                }
                else
                t[i][j]=(t[i-1][j]);
            }
        }
        
        return t[arr.size()][sum1];
    }
    int countPartitions(int n, int d, vector<int>& arr) {
        // Code here
        long long int sum=0;
        for(int i: arr){
            sum+=i;
        }
        if((sum+d)%2!=0 || sum<d) return 0;
        long long int sum1=(sum+d)/2;
        sum1 = min(sum1, sum - sum1);
        vector<vector<long long int>> t(n+1,vector<long long int>(sum1+1));
        return count_no_of_subset(arr,sum1,t);
    }
};

class Solution{
public:
    int kPalindrome(string str, int n, int k)
    {
        vector<vector<int>> dp(n, vector<int>(n, 0));
    
        for (int gap = 1; gap < n; ++gap) {
            for (int i = 0, j = gap; j < n; ++i, ++j) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        int v = dp[0][n-1];
        return v <= k;
    }
};

class Solution {
public:
    int countStations(double maxDist, vector<int> &arr) {
        int cnt = 0, n = arr.size();
        
        for(int i = 0; i < n - 1; i++) {
            double stationsInBetween = ((double) arr[i + 1] - arr[i]) / maxDist;
            cnt += (int) stationsInBetween;
        }
        
        return cnt;
    }

    double findSmallestMaxDist(vector<int> &arr, int k) {
        int n = arr.size();
        double maxi = INT_MIN;
        
        for(int i = 1; i < n; i++)
            maxi = max(maxi, (double) arr[i] - arr[i - 1]);
            
        double low = 0, high = maxi, diff = 0.000001;
        while(high - low > diff) {
            double mid = low + (high - low) / 2;
            
            if(countStations(mid, arr) <= k)
                high = mid;
            else
                low = mid;
        }
        
        return high;
    }
};

class Solution { 
  public: 
    int findCrossOver(vector<int>& arr, int low, int high, int x) { 
        // Base cases 
        if (arr[high] <= x) return high; 
        if (arr[low] > x) return low; 
 
        int mid = (low + high) / 2; 
 
        // Check if mid is the crossover point 
        if (arr[mid] <= x && arr[mid + 1] > x) return mid; 
        else if (arr[mid] < x) return findCrossOver(arr, mid + 1, high, x); 
        return findCrossOver(arr, low, mid - 1, x); 
    } 
 
    // Function to print K closest elements 
    vector<int> printKClosest(vector<int>& arr, int n, int k, int x) { 
        // Find the crossover point 
        int crossoverIndex = findCrossOver(arr, 0, n - 1, x); 
        int leftIndex = crossoverIndex; 
        int rightIndex = crossoverIndex + 1; 
 
        // If the element is present, move left index back 
        if (leftIndex >= 0 && arr[leftIndex] == x) leftIndex--; 
 
        vector<int> closestElements; 
        for (int i = 0; i < k; i++) { 
            // Both indices are valid 
            if (leftIndex >= 0 && rightIndex < n) { 
                int leftDiff = x - arr[leftIndex]; 
                int rightDiff = arr[rightIndex] - x; 
                // Choose the closer element 
                if (leftDiff < rightDiff) { 
                    closestElements.push_back(arr[leftIndex]); 
                    leftIndex--; 
                } else { 
                    closestElements.push_back(arr[rightIndex]); 
                    rightIndex++; 
                } 
            } else if (leftIndex >= 0) { // Only left index is valid 
                closestElements.push_back(arr[leftIndex]); 
                leftIndex--; 
            } else { // Only right index is valid 
                closestElements.push_back(arr[rightIndex]); 
                rightIndex++; 
            } 
        }  
        return closestElements; 
    } 
};

class Solution
{
    public:
        long long int PowMod(long long int x,long long int n,long long int M)
        {
            if(n == 0) return 1;
            long long int mul =PowMod(x,n/2,M);
            if(n&1) return ((x*mul)%M)*mul%M;
            else return mul*mul%M;
        }
};

class Solution{
    public:
    int findClosest( int n, int k,int arr[]) 
    { 
        int lower = lower_bound(arr,arr +n,k) - arr;
        if(lower == 0){
            return arr[lower];
        }
        else if(abs(arr[lower] - k) > abs(arr[lower - 1] - k)){
            return arr[lower - 1];
        }
        return arr[lower];
    } 
};

class Solution {
public:
    int findPeakElement(vector<int>& a) 
    {
        int n = a.size();
        int ans = 0;
        int low = 0;
        int high = n-1;

        
        while(low <= high){
            int mid = low + (high-low)/2;
            
            ans = max(ans, a[mid]);
            
            if(mid+1 < n && a[mid] < a[mid+1]){
                low = mid+1;
            }
            else{
                high = mid-1;
            }
        }
        return ans;
    }
};

class Solution {
public:
    int findPair(int n, int x, vector<int> &arr) {
        unordered_map<int, int> mp;
        
        for(auto num: arr) {
            if(mp.count(num - x) or mp.count(x + num))
                return 1;
                
            mp[num]++;
        }
        
        return -1;
    }
};

class Solution {
public:
    
    int ans=0;
    
    void dfs(int node,int par,vector<int> adj[],vector<int>& size){
        for(auto it:adj[node]){
            if(it==par) continue;
            dfs(it,node,adj,size);
            size[node]+=size[it];
            if(size[it]%2==0) ans++;
        }
    }
    
    int minimumEdgeRemove(int n, vector<vector<int>>edges){
        vector<int> adj[n];
        
        for(auto it:edges){
            adj[it[0]-1].push_back(it[1]-1);
            adj[it[1]-1].push_back(it[0]-1);
        }
        vector<int> size(n,1);
        dfs(0,-1,adj,size);
        return ans;
    }
};