Why is the answer to this problem always ( N + K — 3) / (K — 1).
Can anyone please help me. editorial is not clear.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 162 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 151 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Why is the answer to this problem always ( N + K — 3) / (K — 1).
Can anyone please help me. editorial is not clear.
Name |
---|
In each operation, you will select K numbers. Among them one number must be 1, so the remaining K-1 elements will be replaced by 1. That's why after each operation, you will replace K-1 more numbers by 1.
Among N numbers there is already a 1, so you need to replace remaining N-1 numbers by 1.
So, total required operations = (N-1)/(K-1) But if (N-1) is not divisible by (K-1) you need one more operation.
So, answer is ceil((N-1)/(K-1)). Now calculating ceil of a division X/Y is equivalent to (X+Y-1)/Y
That's why you can write ceil((N-1)/(K-1)) = (N-1 + K-2)/(K-1) = (N+K-3)/(K-1)
Could you please explain how in every step you turn k-1 more numbers into 1. My doubt is that if you reach the start or the end of the array you may not be able to change k-1 as you would actually be considering elements which have already turned 1
Upd: i understood