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 isstrictly greater thannums[i].
The student is not selected and the total number of selected students is strictlyless thannums[i].
Return the number of ways to select a group of students so that everyone remains happy.
Input: nums =[1,1]Output: 2Explanation:
The two possible ways are:The classteacher selects no student.The classteacher selects both students to form the group.If the classteacher selects just one student to form a group then the both students will not be happy. Therefore, there are only two possible ways.
Input: nums =[6,0,3,3,6,7,2,7]Output: 3Explanation:
The three possible ways are:The classteacher selects the student with index =1 to form the group.The classteacher selects the students with index =1,2,3,6 to form the group.The classteacher selects all the students to form the group.
Sort the array. For each possible group size k (from 0 to n), check if all students are happy: those selected (k students) must have k > nums[i], and those not selected (n-k students) must have k < nums[i].
classSolution {
public:int countWays(vector<int>& nums) {
int n = nums.size(), ans =0;
sort(nums.begin(), nums.end());
if (nums[0] >0) ans++;
for (int k =1; k < n; ++k) {
if (nums[k-1] < k && k < nums[k]) ans++;
}
if (nums[n-1] < n) ans++;
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import"sort"funccountWays(nums []int) int {
n, ans:= len(nums), 0sort.Ints(nums)
ifnums[0] > 0 {
ans++ }
fork:=1; k < n; k++ {
ifnums[k-1] < k&&k < nums[k] {
ans++ }
}
ifnums[n-1] < n {
ans++ }
returnans}
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;
classSolution {
publicintcountWays(int[] nums) {
int n = nums.length, ans = 0;
Arrays.sort(nums);
if (nums[0]> 0) ans++;
for (int k = 1; k < n; ++k) {
if (nums[k-1]< k && k < nums[k]) ans++;
}
if (nums[n-1]< n) ans++;
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
funcountWays(nums: IntArray): Int {
val n = nums.size
nums.sort()
var ans = 0if (nums[0] > 0) ans++for (k in1 until n) {
if (nums[k-1] < k && k < nums[k]) ans++ }
if (nums[n-1] < n) ans++return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution:
defcountWays(self, nums: list[int]) -> int:
n = len(nums)
nums.sort()
ans =0if nums[0] >0:
ans +=1for k in range(1, n):
if nums[k-1] < k < nums[k]:
ans +=1if nums[-1] < n:
ans +=1return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
structSolution;
impl Solution {
pubfncount_ways(nums: Vec<i32>) -> i32 {
letmut nums = nums;
nums.sort();
let n = nums.len();
letmut ans =0;
if nums[0] >0 { ans +=1; }
for k in1..n {
if nums[k-1] < k asi32&& k asi32< nums[k] {
ans +=1;
}
}
if nums[n-1] < n asi32 { ans +=1; }
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
countWays(nums: number[]):number {
nums.sort((a, b) =>a-b);
constn=nums.length;
letans=0;
if (nums[0] >0) ans++;
for (letk=1; k<n; ++k) {
if (nums[k-1] <k&&k<nums[k]) ans++;
}
if (nums[n-1] <n) ans++;
returnans;
}
}