Given a binary string persons where ‘1’ and ‘0’ represent people entering and leaving a room respectively. The task is to find the Minimum and Maximum Distinct Persons entering or leaving the building.
Examples:
Input: “000”
Output: Minimum Persons: 3
Maximum Persons: 3
Explanation: 3 distinct persons left the building.Input: “111”
Output: Minimum Persons: 3
Maximum Persons: 3
Explanation: 3 distinct persons entered the building.Input: “110011”
Output: Minimum Persons: 2
Maximum Persons: 6
Explanation: 2 persons entered->those 2 persons left->same 2 persons entered
to account for minimum 2 persons.
All persons entered or left are distinct to account for maximum 6 persons.Input: “10101”
Output: Minimum Persons: 1
Maximum Persons: 5
Explanation: 1 person entered- > he left -> again entered -> again left -> and again entered
to account for minimum 1 person.
All persons entered or left are distinct to account for maximum 5 persons.
Approach: The problem can be solved based on the following observation:
- Each person entering or leaving the room can be a unique person. This will give the maximum number of persons that can enter a room. This will be equal to the total number of times a leaving or entering operation is performed,
- Each time the same persons who are leaving the room are entering the room next time. So the maximum among the people leaving at a time or entering at a time is the minimum possible number of unique persons.
Follow the below illustration for a better understanding.
Illustration:
Consider persons = “10101”
For finding the maximum:
=> At first, first person (say P1) enters the room
=> Then, second person (say P2) exits the room
=> Then, third person (say P3) enters the room
=> Then, fourth person (say P4) exits the room
=> At last, fifth person (say P5) enters the roomTotal 5 persons enter or leave the room at most.
For finding the minimum possible persons:
=> At first, first person (say P1) enters the room.
=> Then P1 exits the room.
=> Then P1 again enters the room.
=> Then again P1 exits the room.
=> At last P1 again enters the room.So at least one person enters or leaves the room.
Follow the below steps to implement the above observation:
- Start traversing the whole string persons.
- If persons[i] = ‘1’ then increment entered else decrement entered.
- Store the maximum value of entered and N (size of string persons) as the first and second value of the pair result.
- In that loop, if at anytime entered becomes negative then re-initialize it to 0 and increment the first value of the pair result.
- Return result as the final pair containing minimum and maximum distinct persons as first and second value respectively.
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum and// maximum number of possible persons// entering or leaving the roompair<int,int> minDistPersons(string& persons){ int N=persons.length(),entered=0; pair<int,int>result={0,N}; for(int i=0;i<N;i++) { if(persons[i]=='1') entered++; else entered--; result.first=max(result.first,entered); if(entered<0) { entered=0; result.first++; } } return result;}// Driver codeint main(){ string persons = "10101"; // Function call pair<int, int> ans = minDistPersons(persons); cout << "Minimum Persons: " << ans.first << "\n"; cout << "Maximum Persons: " << ans.second; return 0;}// this code is contributed by prophet1999 |
Java
// Java code to implement the approachimport java.io.*;class GFG{ // Function to find the minimum and // maximum number of possible persons // entering or leaving the room public static int[] minDistPersons(String persons) { int N = persons.length(); int entered = 0; int result[] = new int[2]; result[1] = N; for (int i = 0; i < N; i++) { if (persons.charAt(i) == '1') entered++; else entered--; result[0] = Math.max(result[0],entered); if(entered<0) { entered=0; result[0]++; } } return result; } // Driver Code public static void main(String[] args) { String persons = "10101"; // Function call int ans[] = minDistPersons(persons); System.out.println("Minimum Persons: " + ans[0]); System.out.print("Maximum Persons: " + ans[1]); }}// this code is contributed by prophet1999 |
Python
# Python3 code for the above approach# Function to find the minimum and# maximum number of positive persons# entering or leaving the roomdef minDistPersons(persons): N = len(persons) entered, exited = 0, 0 result = [0, N] for i in range(N): if persons[i] == "1": entered+=1 else: entered-=1 result[0] = max(result[0], entered) if(entered<0): entered=0 result[0]+=1 return result# Driver Codepersons = "10101"# Function callans = minDistPersons(persons)print("Minimum Persons: " + str(ans[0]))print("Maximum Persons: " + str(ans[1]))# this code is contributed by prophet1999 |
C#
// C# program for above approachusing System;class GFG{ // Function to find the minimum and // maximum number of possible persons // entering or leaving the room public static int[] minDistPersons(string persons) { int N = persons.Length; int entered = 0; int[] result = new int[2]; result[1] = N; for (int i = 0; i < N; i++) { if (persons[i] == '1') entered++; else entered--; result[0] = Math.Max(result[0],entered); if(entered<0) { entered=0; result[0]++; } } return result; }// Driver Codepublic static void Main(){ string persons = "10101"; // Function call int[] ans = minDistPersons(persons); Console.WriteLine("Minimum Persons: " + ans[0]); Console.Write("Maximum Persons: " + ans[1]);}}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code for the above approach // Function to find the minimum and // maximum number of possible persons // entering or leaving the room function minDistPersons(persons) { let N = persons.length; let entered = 0; let result = [0, N]; for (let i = 0; i < N; i++) { if (persons[i] == '1') entered++; else entered--; result[0] = Math.max(...[result[0], entered]); if(entered<0) { entered=0; result[0]++; } } return result; } // Driver code let persons = "10101"; // Function call let ans = minDistPersons(persons); document.write("Minimum Persons: " + ans[0] + '<br>'); document.write("Maximum Persons: " + ans[1]); // this code is contributed by prophet1999 </script> |
Minimum Persons: 1 Maximum Persons: 5
Time Complexity: O(N), where N is the length of the string persons.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
