Lunch boxes - determine the maximum number of schools that can get lunch boxes (Easy)

Index of "Algorithms: Design and Analysis"
<<< Previous    Next >>>

Solve on HackerEarth

Problem

Alice works as a restaurant manager. The restaurant has prepared 
 lunch boxes and Alice plans to distribute them to some schools. Consider that there are 
 schools and an 
 school orders 
 lunch boxes.

She wants to distribute lunch boxes to as many schools as possible. Also, she has the following rule:

For an 
 school, she gives either zero or 
 lunch boxes
Your task is to help Alice to determine the maximum number of schools that can get lunch boxes.

Input format

The first contains an integer 
 that denotes the number of test cases in the input.
Each test case consists of two lines:
The first line contains two integers 
 and 
.
The second line contains 
 integers 
.
Output format

For each test case, you are required to print one integer that represents the maximum number of schools that can receive lunch boxes.

Constraints




Sample Input
2
10 4
3 9 4 2
5 6
3 2 1 1 2 1
Sample Output
3
4
Time Limit: 1
Memory Limit: 256
Source Limit:

Explanation

In first test case 1,3,4 schools got lunch-boxes.

In second test case 3,4 and 2(or 5) schools got lunch boxes.

---

---

My Code

def solve(N, M, A):
    A = sorted(A)

    n = N
    cnt = 0

    for a in A:
        n -= a
        if n >= 0:
            cnt += 1
        else:
            break
    return cnt



t = int(input())

for _ in range(t):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    print(solve(N, M, A))

---

---

Prompting ChatGPT to highlight the concepts sought by the problem

I am learning Data Structures and Algorithms.

I will provide a screenshot of a problem statement. 

Your task is NOT to directly give me the final code solution unless I explicitly ask for it.

Instead, please do the following:

1. First, carefully restate the problem in your own words to confirm correct understanding.
   - If anything is unclear in the screenshot, ask me clarification questions before proceeding.

2. Identify:
   - What category of problem this is (e.g., prefix sum, greedy, DP, two pointers, binary search, graph, etc.)
   - What core DSA concepts are being tested
   - What mathematical observations (if any) are involved
   - What constraints are important and how they affect the approach

3. Explain:
   - What naive/brute-force solution would look like
   - Why that may or may not work under the given constraints
   - What optimization insight is required

4. Clearly explain the key trick or insight needed to solve it.
   - Why does that trick work?
   - What pattern should I remember for future problems?

5. Provide:
   - The time complexity and space complexity of the optimal approach
   - Why it satisfies the constraints

6. If there are multiple valid approaches, compare them.

7. Only after all conceptual explanation, provide clean and correct Python code.

8. Avoid guessing unclear details.
   - If any part of the screenshot is ambiguous, ask me instead of assuming.

Focus on correctness over speed. Be explicit in reasoning.

---

---

...

📌 Core Concepts Being Tested

# Greedy strategy

# Sorting

# Resource allocation

# Knapsack intuition (but simplified)

...