The apples can be shared with anyone. Instead of giving an apple to someone only when he needs, we can split the apples equally among all the people at the beginning.
This can be done by finding the total number of apples and dividing by N, to find the average number of apples each person should have.
We do not need the array after this. The average is sufficient to find the solution.
The average can be a floating point value like 2.5, but a person can’t have half an apple.
If we find the greatest integer less than or equal to the average (also called as floor), then it gives the day on which the first person dies. eg: floor(2.9)=2
If we find the smallest integer greater than or equal to the average (also called as ceil), then it gives the day on which the last person dies. eg: ceil(2.1)=3
This solution has a complexity of O(n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Both use the same approach.