Untitled

========= Q1 ==========
class Solution {
public:
    int minAbsoluteDifference(vector<int>& nums) {
        int n=nums.size(),ans=-1;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(nums[i]==1 && nums[j]==2){
                    int diff=abs(i-j);
                    if(ans==-1 || ans>diff) ans=diff;
                }
            }
        }
        return ans;
    }
};

========= Q2 ==========
#define ll long long int
const ll mod=1e9+7;
// module inverse
ll mi(ll n,ll m){ll pw=n%m;ll ex=m-2;ll ans=1;while(ex){if(ex&1) ans = ans*pw%m;pw = pw*pw%m;ex>>=1;}return ans%mod;}
class Solution {
public:
    int countVisiblePeople(int n, int pos, int k) {
        vector<ll> fac(n+1);
        fac[0]=1;
        for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
        int left=pos;
        int right=n-left-1;
        ll ans=0;
        for(int l=0;l<=k;l++){
            int r=k-l;
            if(l<=left && r<=right){
                // leftCl * rightCr
                ll waysL=(fac[left]*mi(fac[l],mod)%mod)*mi(fac[left-l],mod)%mod; // fac[left]/(fac[l]*fac[left-l])
                ll waysR=(fac[right]*mi(fac[r],mod)%mod)*mi(fac[right-r],mod)%mod; 
                ans=(ans+waysL*waysR)%mod;
            }
        }
        return ans*2%mod;
    }
};

========= Q3 ==========
class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int dp[m][n][1024];
        // dp[i][j][k]=1 means there exist a path from (0,0) -> (i,j) such that the bitwise XOR value of all numbers along the path is exactly = k
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<1024;k++) dp[i][j][k]=-1;
            }
        }
        dp[0][0][grid[0][0]]=1;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<1024;k++){
                    if(i>=1 && dp[i-1][j][k]!=-1) dp[i][j][k^grid[i][j]]=1;
                    if(j>=1 && dp[i][j-1][k]!=-1) dp[i][j][k^grid[i][j]]=1;
                }
            }
        }
        for(int i=0;i<1024;i++){
            if(dp[m-1][n-1][i]!=-1) return i;
        }
        assert(false);
        return -1;
    }
};

========= Q4 ==========
class Solution {
public:
    int countArrays(vector<int>& digitSum) {
        int n=digitSum.size();
        unordered_map<int,vector<int>> mp;
        for(int i=0;i<=5000;i++){
            int dsum=0,z=i;
            while(z) dsum+=(z%10),z/=10;
            mp[dsum].push_back(i);
        }
        const int mod=1e9+7;
        vector<unordered_map<int,int>> dp(n);
        for(int x:mp[digitSum[0]]) dp[0][x]=1;
        for(int i=1;i<n;i++){
            auto v1=mp[digitSum[i-1]];
            int m=v1.size();
            if(m>0){
                vector<int> pre(m);
                pre[0]=dp[i-1][v1[0]];
                for(int j=1;j<m;j++){
                    pre[j]=(pre[j-1]+dp[i-1][v1[j]])%mod;
                }
                auto v2=mp[digitSum[i]];
                for(int x:v2){
                    int idx=(upper_bound(v1.begin(),v1.end(),x)-v1.begin())-1;
                    if(idx>=0){
                        dp[i][x]+=pre[idx];
                        dp[i][x]%=mod;
                    }
                }
            }
        }
        int ans=0;
        for(int x:mp[digitSum.back()]) ans=(ans+dp[n-1][x])%mod;
        return ans;
    }
};