Sufficient Food for Rats

Easy

0/40

Contributed by

0 upvote

Problem statement

An exterminator is planning to deploy food bait for a population of rats in a residential area. You are given the number of rats, the amount of food each rat consumes, and a list representing the amount of food available in a sequence of houses.

Your task is to find the minimum number of houses, starting from the first house and proceeding in order, that must be checked to collect enough food for all the rats.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer r, the number of rats.

The second line contains an integer unit, the amount of food one rat consumes.

The third line contains an integer n, the number of houses.

The fourth line contains n space-separated integers, representing the array arr where arr[i] is the amount of food in house i+1.

Output Format:

The output should be a single integer based on the following rules:
- Return the total number of houses required to feed all the rats.

- Return 0 if the total amount of food from all houses is not sufficient.

- Return -1 if the input array is null or empty (n = 0).

Note:

The total food required is r * unit.

You must accumulate food starting from the first house (arr[0]) and move sequentially.

The problem asks for the count of houses, which is a 1-based index.

Sample Input 1:

7
2
8
2 8 3 5 7 4 1 2

Sample Output 1:

Explanation for Sample 1:

1. Total food required: r * unit = 7 * 2 = 14.

2. Start accumulating food from the houses:
- House 1: Food = 2. (Total collected: 2. Not enough.)

- House 2: Food = 8. (Total collected: 2 + 8 = 10. Not enough.)

- House 3: Food = 3. (Total collected: 10 + 3 = 13. Not enough.)

- House 4: Food = 5. (Total collected: 13 + 5 = 18. This is >= 14.)

3. Since we have enough food after checking the 4th house, the answer is 4.

Expected Time Complexity:

The expected time complexity is O(N), where N is the number of houses.

Constraints:

r, unit, n are positive integers.
0 <= n <= 10^5
1 <= arr[i] <= 1000

Time limit: 1 sec

Approaches (1)

Approach 1

Cumulative Sum Iteration

Time Complexity

Space Complexity

(100% EXP penalty)

Sufficient Food for Rats

Console