Happy Students - Practice Coding Problems

Happy Students - Problem

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 i^th 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.

Input & Output

Example 1 — Simple Case

$ Input: nums = [1,1]

› Output: 1

💡 Note: Only one way works: select no students. Both students are happy because 0 < 1, so they're satisfied being unselected.

Example 2 — Multiple Options

$ Input: nums = [6,0,3,3,6,7,2,3]

› Output: 3

💡 Note: Three valid selection sizes work: selecting 0 students, 4 students, or 7 students can make everyone happy.

Example 3 — No Solution

$ Input: nums = [1,2,3]

› Output: 0

💡 Note: No selection size can satisfy all students simultaneously due to conflicting requirements.

Constraints

1 ≤ nums.length ≤ 50
0 ≤ nums[i] < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of student expectations nums=[1,1]

Process

Try each possible selection size and check happiness

Output

Count ways to make everyone happy: 1

Key Takeaway

🎯 Key Insight: The total selection count is the key constraint, not which specific students are chosen

Asked in

G Google 12 f Meta 8 a Amazon 6

The key insight is that student happiness depends on the total selection count, not specific individuals selected. We can enumerate each possible selection size k and check if all constraints can be satisfied. Best approach uses mathematical categorization to count valid arrangements efficiently. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Enumerate Valid Sizes	O(n²)	O(1)	Sort the array and systematically check which selection sizes can work
Optimized Enumeration with Early Pruning	O(n²)	O(1)	Smart enumeration that skips impossible cases and uses mathematical insights
Brute Force - Try All Combinations	O(n × 2^n)	O(1)	Generate all possible subsets and check if each makes everyone happy

Sort and Enumerate Valid Sizes — Algorithm Steps

Sort the array to organize students by requirements
For each possible selection size k from 0 to n
Check if we can satisfy all students with this size
Count valid arrangements for each feasible size

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Size k

For each possible selection size from 0 to n

Check Constraints

Count students who must/must not be selected

Count Ways

Calculate combinations for flexible students

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long combination(int n, int r) {
    if (r > n || r < 0) return 0;
    if (r == 0 || r == n) return 1;
    
    long long result = 1;
    for (int i = 0; i < r; i++) {
        result = result * (n - i) / (i + 1);
    }
    return result;
}

int solution(int* nums, int n) {
    long long count = 0;
    
    // Try each possible selection size
    for (int k = 0; k <= n; k++) {
        int mustSelect = 0;
        int mustNotSelect = 0;
        
        for (int i = 0; i < n; i++) {
            if (k <= nums[i]) mustSelect++;
            if (k >= nums[i]) mustNotSelect++;
        }
        
        if (mustSelect <= k && mustNotSelect <= n - k) {
            int remainingToSelect = k - mustSelect;
            int flexibleStudents = n - mustSelect - mustNotSelect;
            
            if (remainingToSelect <= flexibleStudents && remainingToSelect >= 0) {
                if (flexibleStudents == 0) {
                    count += 1;
                } else {
                    count += combination(flexibleStudents, remainingToSelect);
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sort takes O(n log n), then O(n) sizes × O(n) validation per size

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting, sorting in-place

✓ Linear Space

8.9K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Enumerate Valid Sizes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler