Given an array of N size denotes number of students and element of array denotes marks of students ,marks belongs between 1 to 100, where A[i] is less or equal to 32 denotes that student was fail and A[i] grater or equal to 91 denotes it was passed with hons.
The task is to find minimum number of room allotted their all student who are fulfill the condition given blow.
Conditions 1. If student was fail then not allot the room. 2. If passed with hons then he was stay single in a room. 3.
If student obtain 33 to 90 marks then they are stay double in a room.
Examples:
Input :
a[] = {23, 56, 89, 34, 67, 54, 56}
Output :
3
Since total student are 7 ,and one student get 23 marks that student fail
and not apply for hostel, other six student are passed and marks in range of 33 to 90
So they are stay in double in a room, hence minimum number of room allotted is 3.
Input :
A[] = {24, 1, 8, 32, 45, 45, 45, 67, 87, 96, 75, 96, 98, 96, 96}
Output :
8
Approach:
Since the problem has a restriction on array if any element are lesser then 33 then no room allotted, if grater then 90 then count one by one if 33 to 90 then its count two in one.
Below is the implementation of the above approach:
// C++ program for the minimum number
// of rooms required
#include <bits/stdc++.h>
using namespace std;
// Find the minimum number of rooms required
int minimumRoomRequired(int a[], int N)
{
int i, b[2] = {0}, sum = 0, m;
// Initialize hash array b[2] with 0
for (i = 0; i < N; i++)
{
if (a[i] < 33)
// If less than 33,
// the student fails
continue;
else if (a[i] >= 33 && a[i] <= 90)
// Count marks between 33 and 90
b[0]++;
else
// Count marks above 90
b[1]++;
}
b[0] = (b[0] + 1) / 2;
sum = b[1] + b[0];
return sum;
}
// Main driver function
int main()
{
int a[] = {32, 56, 76, 54, 87, 56, 98, 34, 65, 56, 91, 91};
cout << minimumRoomRequired(a, sizeof(a) / sizeof(a[0])) << endl;
// Call the function and
// print how many rooms are required
return 0;
}
Output:
7
Time Complexity: O(N)