DIFFICULTY:
EASY
PREREQUISITES:
Math
Problem link:
PROBLEM:
There are N children in the question playing hide and seek. In each round, one of them seeks and others hide.
You are given an array H of N numbers where H[i] represents the minimum number of rounds ith child have to hide to be satisfied. (1 based Indexing)
We aim to determine the least number of rounds that need to be played so that every child is satisfied.
EXPLANATION:
Let’s say the number of rounds played is M. Now, the ith child can seek in at most (M - H[i]) rounds. ( 1 based Indexing) . And the summation of the number of rounds every child seeks has to be equal to M. So, we can have the following derivation based on upper observations.
\sum_{i = 1}^{N}(M - H_i) \geq M
(M*N - \sum_{i = 1}^{N} H_i ) \geq M
(M*N - \sum_{i = 1}^{N} H_i - M) \geq 0
(M*(N-1) - \sum_{i = 1}^{N} H_i ) \geq 0
(M*(N-1) - \sum_{i = 1}^{N} H_i ) \geq 0
M \geq \dfrac{\sum_{i = 1}^{N} H_i } { (N-1)}
Now, using ceiling function, we can have the minimum estimation of M, that is,
M_1 = ceil(\frac{ \sum_{i = 1}^{N} H_i }{N-1} )
But there has to be at least M2 rounds of play where,
M_2 = max(H_i) ; i \epsilon [1,n]
Final answer will be,
M = max(M_1,M_2)
SOLUTIONS:
a.
N = 7
\sum_{i = 1}^{N} H_i = 65
M_1 = ceiling(65/6) = 11
M_2 = max(H[i]) = 15
M = max(M_1 , M_2) = 15
b.
N = 12
\sum_{i = 1}^{N} H_i = 100
M_1 = ceiling(100/11) = 10
M_2 = max(H[i]) = 9
M = max(M_1 , M_2) = 10
c.
N = 15
\sum_{i = 1}^{N} H_i = 2019
M_1 = ceiling(2019/14) = 145
M_2 = max(H[i]) = 140
M = max(M_1 , M_2) = 145