Problem Statement

Given a string S of length N consisting of ‘x’ and ‘.’. The given string represents a row of seats where ‘x’ and ‘.’ represent occupied and unoccupied seats respectively. The task is to minimize the total number of hops or jumps to make all the occupants sit together i.e., next to each other, without having any vacant seat between them.

Note: Since the count of jumps can be very large, print the answer modulo 10^9 + 3.

Examples:

Input: S = “. . . . x . . x x . . . x . .”Output: 5Explanation: Below are the required shuffling of occupants:Step 1: Make the person at 5th seat jump 2 places to the 7th seat.Step 2: Make the person at 13th seat jump 3 places to the 10th seat.Therefore, total number of jumps required = 2 + 3 = 5.Input: S = “x x x . . . . . . . . x x x x x x”Output: 24Explanation: Move the occupants from 1st, 2nd and 3rd position to the 9th, 10th, 11th positions respectively. Therefore, the total number of jumps required = (11 – 3) + (10 – 2) + (9 – 3) = 24.

Problem Link

Seats - InterviewBit

Reference Video

https://www.youtube.com/watch?v=SK2ypa7poKg

Code

#define mod 10000003
int Solution::seats(string A) {
    
    //The idea is to make all the persons to seat around the middle seated person
    //so to minimize the number of jumps required
    int sum = 0;
    int n = A.size();
    int start = 0;
    
    int end = 0;
    vector<int> pos;//stores the original positions of the seated persons
    for(int i=0;i<n;i++)
    {
        if(A[i]=='x')
        {
           pos.push_back(i);
        }
    }
    int sz = pos.size();
    int mid = sz/2;//index of the middle person in the pos array
    if(sz==0)
    return 0;
    
    for(int i=0;i<sz;i++)
    {
        start = pos[i]; //original index of the seated persom
        end = pos[mid]-mid+i;//new index where the person will be seater
        
        sum = (sum%mod + ((abs(end-start))%mod) )%mod;
    }
    
    
    
    return sum%mod;
}