Proof about logarithms

Правка en1, от snorkel, 2021-04-09 00:43:00

Given numbers $$$1$$$ to $$$n$$$, we have to make all those number equal to zero by choosing some subset and subtracting some value from all of them, we have to use minimum number of operations.

My idea was to always split it into two parts and get two {$$$1,2..n/2-1,n/2$$$} sets from {$$$1,2,..n$$$} set and continue like this recursively. This approach is correct and leads to $$$ceil(log_2(n))$$$ solution. What is the proof this being optimal?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский snorkel 2021-04-09 01:35:50 2 Tiny change: 'tracting some value f' -> 'tracting same value f'
en1 Английский snorkel 2021-04-09 00:43:00 454 Initial revision (published)