Brainstorming Quiz - Day 4 Solution

Answer: 9

Explanation of the Approach and Solution:

The task is to calculate the total number of guests who stay at the party based on the given condition: Each guest G stays at the party only if the number of people already at the party (count) is greater than or equal to the requirement P[i] for that guest.

Steps in the Solution:

1. Initialization:
   • Start with count = 0 because initially, there are no guests at the party.
2. Iterate Over the Array:
   • Traverse the array guests[] in the given order of arrival.
   • For each guest i, check if the number of people already at the party (count) meets or exceeds the guest's requirement (P[i]):
     • If yes, the guest stays at the party, and count is incremented by 1.
     • If no, the guest leaves.
3. Output the Total Guests:
   • After iterating through the entire array, count will hold the total number of guests who stayed at the party.

Example Walkthrough:

For the input array P = {0, 1, 7, 9, 2, 1, 0, 1, 3, 4, 9, 8}:

• Guest 0 arrives (requirement = 0). Since count = 0 (meets the requirement), count becomes 1.
• Guest 1 arrives (requirement = 1). count = 1 (meets the requirement), count becomes 2.
• Guest 2 arrives (requirement = 7). count = 2 (does not meet the requirement), guest leaves.
• Continue this process for all guests.

At the end of the loop, count = 6.

Complexity:

• Time Complexity: O(N), as we iterate through the array once.
• Space Complexity: O(1), as we use only a single variable (count) for calculations.

// C++ program to get the
// total number of guests at the party

/**
 * Today a person has a birthday and he decides to hosts a party,person invites 12 guests to it. However,the guest are abstruse,
 * each guest has a condition,
 * the condition is
 *  each guest ‘G’ only stays at the party if there are at least ‘P’ people already at the party,
 *  otherwise they leave by saying bye bye.The array of "P" people are {0,1,7,9,2,1,0,1,3,4,9,8}
 * The task is to find the total number of guests that are present at the party. It is also given that the guests arrive at
 * the party in the order given in the array ‘P’.
 */
#include <bits/stdc++.h>
using namespace std;

// Function to find the totalGuests
int findGuest(int array[], int N)
{
  // Total guest before the party are 0
  int count = 0;

  // Checking requirements for each guest
  for (int i = 0; i < N; i++)
  {

    // If requirements are met
    if (array[i] <= count)
    {

      // The Gi guest decides to stay
      // So increment total guest by 1
      count++;
    }
  }

  // Return the totalnumber of guest
  return count;
}

// Driver code
int main()
{

  // Get the number of guests invited
  int N = 12;

  // Guests array stores
  // the requirement by each guest
  int guests[] = {0, 1, 7, 9, 2, 1, 0, 1, 3, 4, 9, 8};

  // Get the total number of guests present
  int totalGuests = findGuest(guests, N);

  cout << totalGuests << endl;

  return 0;
}