Interviewbit - Seats

help
1

Seats - InterviewBit

int Solution::seats(string A) {
    string s = "."+A+".";
    int n=A.size();
    long long left[n+5],right[n+5];
    int cnt=0,mod=10000003;
    
    left[0]=0,right[n+1]=0;
    
    
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='x')
        {
            cnt++;
            left[i]=left[i-1];
        }
        else
        left[i]=left[i-1]+cnt;
    }
    cnt=0;
    for(int i=n;i>=1;i--)
    {
        if(s[i]=='x')
        {
            cnt++;
            right[i]=right[i+1];
        }
        else
        right[i]=right[i+1]+cnt;
    }
    long long ans=LONG_MAX;
    
    
    for(int i=0;i<=n;i++)
    ans=min(ans, (left[i]+right[i+1])%mod);
    
    
    return ans;
}
//  . . . . x . . x x . . . x . .

Is this approach wrong?

2

My idea is just to greedily bring everything to the median

CODE 
const int M = 1e7+3 ;
int Solution::seats(string S) {
    vector<int>A ;
    for(int i=0;i<S.size();i++)
        if(S[i]=='x')
            A.push_back(i) ;
    int N =A.size(),ans=0 ;
    for(int i=0;i<N;i++)
        (ans+=abs(A[N/2]-A[i])-abs(N/2-i))%=M ;
    return ans  ;
}

Your approach is definitely correct, at least for small test cases. Seems like they have a nasty edge case for which your code is failing.

3

What are the constraints ? :sweat_smile: I was unable to find them as I don’t use interview bit

5

Alright got it, there’s a very deceptive bug in your code. Notice one thing you actually want the minimum value of left[i]+right[i+1] not (left[i]+right[i+1])%mod, do you see the difference ?

This passes 
int Solution::seats(string A) {
    string s = "."+A+".";
    int n=A.size();
    long long left[n+5],right[n+5];
    int cnt=0,mod=10000003;
    
    left[0]=0,right[n+1]=0;
    
    
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='x')
        {
            cnt++;
            left[i]=left[i-1];
        }
        else
        left[i]=left[i-1]+cnt;
    }
    cnt=0;
    for(int i=n;i>=1;i--)
    {
        if(s[i]=='x')
        {
            cnt++;
            right[i]=right[i+1];
        }
        else
        right[i]=right[i+1]+cnt;
    }
    long long ans=LONG_MAX;
    
    
    for(int i=0;i<=n;i++)
    ans=min(ans, left[i]+right[i+1]);
    
    
    return ans%mod;
}
2 Likes