Problem Description
You are a caretaker of a waiting room and you have to take care of empty seats such that all the people should sit together. Imagine the seats are in a straight line like in a movie theatre. People are seated on random seats initially. Your task is to make them sit together so that minimum number of people change their position. Also, they can be made to sit together in many ways. Find the number of ways you can make them sit together by requiring only minimal people movement.
“E” depicts an empty seat and “O” depicts an occupied seat. Input will be given in the form of a string.
Example: OEOEO
As we can see, only seat number 1, 3, 5 are occupied and 2 and 4 are empty.
Case 1: If we move 5th person to 2nd position, they can all be together with only one person moving his/her place.
Case 2: If we movement 1st person to 4th position, they can all be together with only one person moving his/her place.
They can all be together with only one movement and this can be done in 2 ways. Print the minimum number of movements required and the number of ways this minimum movement can help achieve the objective.
Note: If they are already sitting together, Print “00” as output.
Constraints
0
Input
First line contains an integer N which depicts the number of seats
Second line contains N characters each of which are either “O” or “E”. “O” denotes an occupied seat and “E” denotes an empty seat.
Output
Print minimum number of movements required and the number of ways in which all people can be made to sit together without exceeding minimum number of movements by space
Time Limit (secs)
1
Examples
Input
5
OEOEO
Output
1 2
Explanation:
Given data of 5 seats in the queue,
Seat number 2 and 4 are unoccupied and all the other seats are occupied.
We can make them sit together by moving only one person near to the other. It can be done in 2 ways:
OOOEE (Moving 4 person to 2 position)
EE000 (Moving 1 person to 4 position)
Solution in C:
#include <stdio.h>
#include <string.h>
int* minMovesTogether(char seats[]);
int main() {
int N;
scanf("%d", &N); // Input number of seats
char seats[N+1];
scanf("%s", seats); // Input seat arrangement
int *result = minMovesTogether(seats);
printf("%d %d\n", result[0], result[1]);
return 0;
}
int* minMovesTogether(char seats[]) {
int occupied = 0;
int length = strlen(seats);
for (int i = 0; i < length; i++) {
if (seats[i] == 'O') {
occupied++;
}
}
if (occupied == 0 || occupied == length) {
static int zeros[2]; // Static array to hold return values
zeros[0] = 0;
zeros[1] = 0;
return zeros;
}
int emptyCounts[length];
memset(emptyCounts, 0, sizeof(emptyCounts));
int currentAvailable = 0;
int index = 0;
for (int i = 0; i < length; i++) {
if (seats[i] == 'E') {
currentAvailable++;
} else {
if (currentAvailable > 0) {
emptyCounts[index++] = currentAvailable;
}
currentAvailable = 0;
}
}
int minEmptySeats = __INT_MAX__;
for (int i = 0; i < index; i++) {
if (emptyCounts[i] < minEmptySeats) {
minEmptySeats = emptyCounts[i];
}
}
int minMoves = minEmptySeats - 1;
int ways = 0;
for (int i = 0; i < index; i++) {
if (emptyCounts[i] == minEmptySeats) {
ways++;
}
}
static int results[2]; // Static array to hold return values
results[0] = minMoves * occupied + 1;
results[1] = ways;
return results;
}
You can also run it on an online IDE:
https://ide.geeksforgeeks.org/online-c-compiler/04270dde-f3c6-4a80-bbb8-69314322c030
No comments:
Post a Comment