We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Happy Students

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array nums of length n where n is the total number of students in the class. The class teacher tries to select a group of students so that all the students remain happy. The ith student will become happy if one of these two conditions is met:

  • The student is selected and the total number of selected students is strictly greater than nums[i].
  • The student is not selected and the total number of selected students is strictly less than nums[i].

Return the number of ways to select a group of students so that everyone remains happy.

Key Insights

  • A student is happy if the number of selected students is either greater than or less than their preference.
  • The total number of selected students can range from 0 to n.
  • Conditions can be checked by sorting the preference array for easier comparison.
  • The result can be derived by counting valid selection sizes based on sorted preferences.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array. Space Complexity: O(1) - no additional space used apart from input/output.

Solution

To solve the problem, we will:

  1. Sort the array nums to facilitate comparison.
  2. Iterate through the sorted array and determine valid selection sizes based on the preferences.
  3. Count the number of valid selection sizes that keep all students happy.

The algorithm relies on sorting to enable efficient checks against the conditions for happiness.

Code Solutions

def happy_students(nums):
    nums.sort()
    n = len(nums)
    count = 0

    for k in range(n + 1):
        # Check if k (number of selected students) can satisfy all students
        if (k == 0 and nums[0] > 0) or (k > 0 and k > nums[k - 1] and (k == n or k <= nums[k])):
            count += 1

    return count

# Example usage
print(happy_students([1, 1]))  # Output: 2
print(happy_students([6, 0, 3, 3, 6, 7, 2, 7]))  # Output: 3
← Back to All Questions