Skip to content

2860. Happy Students

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.

 

Example 1:

Input: nums = [1,1]
Output: 2
Explanation: 
The two possible ways are:
The class teacher selects no student.
The class teacher selects both students to form the group. 
If the class teacher selects just one student to form a group then the both students will not be happy. Therefore, there are only two possible ways.

Example 2:

Input: nums = [6,0,3,3,6,7,2,7]
Output: 3
Explanation: 
The three possible ways are:
The class teacher selects the student with index = 1 to form the group.
The class teacher selects the students with index = 1, 2, 3, 6 to form the group.
The class teacher selects all the students to form the group.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] < nums.length

Solutions

Solution 1: Sorting + Enumeration

Assume that \(k\) students are selected, then the following conditions hold:

  • If \(nums[i] = k\), then there is no grouping method;
  • If \(nums[i] > k\), then student \(i\) is not selected;
  • If \(nums[i] < k\), then student \(i\) is selected.

Therefore, the selected students must be the first \(k\) elements in the sorted \(nums\) array.

We enumerate \(k\) in the range \([0,..n]\). For the current number of selected students \(i\), we can get the maximum student number in the group \(i-1\), which is \(nums[i-1]\). If \(i > 0\) and \(nums[i-1] \ge i\), then there is no grouping method; if \(i < n\) and \(nums[i] \le i\), then there is no grouping method. Otherwise, there is a grouping method, and the answer is increased by one.

After the enumeration ends, return the answer.

The time complexity is \(O(n \times \log n)\), and the space complexity is \(O(\log n)\). Here, \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countWays(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        for i in range(n + 1):
            if i and nums[i - 1] >= i:
                continue
            if i < n and nums[i] <= i:
                continue
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int countWays(List<Integer> nums) {
        Collections.sort(nums);
        int n = nums.size();
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            if ((i == 0 || nums.get(i - 1) < i) && (i == n || nums.get(i) > i)) {
                ans++;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int countWays(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i <= n; ++i) {
            if ((i && nums[i - 1] >= i) || (i < n && nums[i] <= i)) {
                continue;
            }
            ++ans;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func countWays(nums []int) (ans int) {
    sort.Ints(nums)
    n := len(nums)
    for i := 0; i <= n; i++ {
        if (i > 0 && nums[i-1] >= i) || (i < n && nums[i] <= i) {
            continue
        }
        ans++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function countWays(nums: number[]): number {
    nums.sort((a, b) => a - b);
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i <= n; ++i) {
        if ((i && nums[i - 1] >= i) || (i < n && nums[i] <= i)) {
            continue;
        }
        ++ans;
    }
    return ans;
}

Comments