Minimum jumps required to make a group of persons sit together
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 109 + 7.
Examples:
Input: S = β. . . . x . . x x . . . x . .β
Output: 5
Explanation: 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: 24
Explanation: 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.
Approach: The idea is to use a Greedy Approach to solve this problem. Observe that it is always optimal to shift the elements towards the median element among the persons or the center person among all the persons present. The number of jumps will always be minimum when we shift points to the median. Below are the steps:
- Initialize a vector position to store the indexes of the persons present.
- Find the median of the vector position[]. All the other persons will now be made to sit around this person as this will give the minimum number of jumps that are required to be made.
- Initialize a variable ans that stores the minimum jumps required.
- Now, traverse the vector position[] and for every index i find the median element and update ans as:
ans= ans+ abs(position[i] β medianElement)
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; long long int MOD = 1e9 + 7; // Function to find the minimum jumps // required to make the whole group // sit adjacently int minJumps(string seats) { // Store the indexes vector< int > position; // Stores the count of occupants int count = 0; // Length of the string int len = seats.length(); // Traverse the seats for ( int i = 0; i < len; i++) { // If current place is occupied if (seats[i] == 'x' ) { // Push the current position // in the vector position.push_back(i - count); count++; } } // Base Case: if (count == len || count == 0) return 0; // The index of the median element int med_index = (count - 1) / 2; // The value of the median element int med_val = position[med_index]; int ans = 0; // Traverse the position[] for ( int i = 0; i < position.size(); i++) { // Update the ans ans = (ans % MOD + abs (position[i] - med_val) % MOD) % MOD; } // Return the final count return ans % MOD; } // Driver Code int main() { // Given arrange of seats string S = "....x..xx...x.." ; // Function Call cout << minJumps(S); return 0; } |
Java
// Java program for the // above approach import java.util.*; class GFG{ static int MOD = ( int )1e9 + 7 ; // Function to find the minimum // jumps required to make the // whole group sit adjacently static int minJumps(String seats) { // Store the indexes Vector<Integer> position = new Vector<>(); // Stores the count of // occupants int count = 0 ; // Length of the String int len = seats.length(); // Traverse the seats for ( int i = 0 ; i < len; i++) { // If current place is occupied if (seats.charAt(i) == 'x' ) { // Push the current position // in the vector position.add(i - count); count++; } } // Base Case: if (count == len || count == 0 ) return 0 ; // The index of the median // element int med_index = (count - 1 ) / 2 ; // The value of the median // element int med_val = position.get(med_index); int ans = 0 ; // Traverse the position[] for ( int i = 0 ; i < position.size(); i++) { // Update the ans ans = (ans % MOD + Math.abs(position.get(i) - med_val) % MOD) % MOD; } // Return the final count return ans % MOD; } // Driver Code public static void main(String[] args) { // Given arrange of seats String S = "....x..xx...x.." ; // Function Call System.out.print(minJumps(S)); } } // This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach MOD = 10 * * 9 + 7 # Function to find the minimum jumps # required to make the whole group # sit adjacently def minJumps(seats): # Store the indexes position = [] # Stores the count of occupants count = 0 # Length of the string lenn = len (seats) # Traverse the seats for i in range (lenn): # If current place is occupied if (seats[i] = = 'x' ): # Push the current position # in the vector position.append(i - count) count + = 1 # Base Case: if (count = = lenn or count = = 0 ): return 0 # The index of the median element med_index = (count - 1 ) / / 2 # The value of the median element med_val = position[med_index] ans = 0 # Traverse the position[] for i in range ( len (position)): # Update the ans ans = (ans % MOD + abs (position[i] - med_val) % MOD) % MOD # Return the final count return ans % MOD # Driver Code if __name__ = = '__main__' : # Given arrange of seats S = "....x..xx...x.." # Function Call print (minJumps(S)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ static int MOD = ( int )1e9 + 7; // Function to find the minimum // jumps required to make the // whole group sit adjacently static int minJumps(String seats) { // Store the indexes List< int > position = new List< int >(); // Stores the count of // occupants int count = 0; // Length of the String int len = seats.Length; // Traverse the seats for ( int i = 0; i < len; i++) { // If current place is // occupied if (seats[i] == 'x' ) { // Push the current // position in the // vector position.Add(i - count); count++; } } // Base Case: if (count == len || count == 0) return 0; // The index of the median // element int med_index = (count - 1) / 2; // The value of the median // element int med_val = position[med_index]; int ans = 0; // Traverse the position[] for ( int i = 0; i < position.Count; i++) { // Update the ans ans = (ans % MOD + Math.Abs(position[i] - med_val) % MOD) % MOD; } // Return the readonly // count return ans % MOD; } // Driver Code public static void Main(String[] args) { // Given arrange of seats String S = "....x..xx...x.." ; // Function Call Console.Write(minJumps(S)); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript program for the above approach let MOD = 1e9 + 7; // Function to find the minimum jumps // required to make the whole group // sit adjacently function minJumps(seats) { // Store the indexes let position = []; // Stores the count of occupants let count = 0; // Length of the string let len = seats.length; // Traverse the seats for (let i = 0; i < len; i++) { // If current place is occupied if (seats[i] == 'x' ) { // Push the current position // in the vector position.push(i - count); count++; } } // Base Case: if (count == len || count == 0) return 0; // The index of the median element let med_index = parseInt((count - 1) / 2, 10); // The value of the median element let med_val = position[med_index]; let ans = 0; // Traverse the position[] for (let i = 0; i < position.length; i++) { // Update the ans ans = (ans % MOD + Math.abs(position[i] - med_val) % MOD) % MOD; } // Return the final count return ans % MOD; } // Driver code // Given arrange of seats let S = "....x..xx...x.." ; // Function Call document.write(minJumps(S)); // This code is contributed by suresh07 </script> |
5
Time Complexity: O(N)
Auxiliary Space: O(N)