Tester: Misha Chorniy
Editorialist: Taranpreet Singh

Easy

### PREREQUISITES:

Prefix sums or anything similar.

### PROBLEM:

Given a group of N people. At day 0, only person 1 knows about Snackdown. Array A is given, A[i] means the number of people ith person will inform. This means, that if at day t, ith person knows about snackdown, exactly A[i] more people will know about Snackdown on day t+1. Find minimum number of days to make sure all N people know about Snackdown.

People spread information in increasing order of position. i.e. If person at position p doesn’t know about Snackdown, all people after position p also won’t know.

### SUPER QUICK EXPLANATION

• Make prefix sum array, call it pre. If x people know about Snackdown on day T, then pre[x] more people will know about Snackdown on day T+1.

### EXPLANATION

First of all, I am explaining a brute force solution, then we’ll optimise it using prefix arrays.

Let us consider naive solution. On day 0, only 1 person knows about snackdown. Next day, X = 1+A people will know. Next day, X = X+A+A + \dots +A[X] people will know. So, we can just increase X by A+A+A+ \dots +A[X]. This process continues till X < N. Let call S = A+A+ \dots +A[X]. Every time, we can calculate S by iterating from index 1 to X.

This process leads to an O(N^2) algorithm.

Now, The thing to speed up above is that, we can calculate S faster than O(N) time by noticing that S is just sum of First X numbers. We can precalculate prefix sum array of given array A, let’s call it pre and Notice that S is just pre[x], thus, computing S in O(1) time, which results in overall O(N) time, which easily fit the time limit.

Also, In case you are not in mood to compute prefix array, it can also be solved by a sum variable, the idea of which is left as an exercize for readers.

### BONUS

• Problem statement states A \geq 1. What happens if A ==0.
• Solve a modified problem. People are not notified in increasing order of position. People who know, can tell anyone. Find minimum as well as maximum number of days it takes for all N people to know about Snackdown.

### Time Complexity

Since We iterate over all elements once, as well as prefix array construction takes linear time, Time complexity is O(N).

Memory complexity is O(N).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Feel free to Share your approach, If it differs. Suggestions are always welcomed. 2 Likes