Given numbers $$$1$$$ to $$$n$$$, we have to make all those number equal to zero by choosing some subset and subtracting same 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?
Hint: prove that, for one operation, if the number of different values in the set was $$$k$$$ before the operation, it will be at least $$$\lceil k / 2 \rceil$$$ after the operation.
I think the middle is optimal because if didn't do middle we would have one smaller and one larger set and the answer will only depend on the larger set, because we do things in parallel.
Is this the correct proof?
More or less.
The important part is this: when we have $$$k$$$ distinct elements, and pick $$$p$$$ elements to decrease, there are $$$k - p$$$ old elements which will still be distinct, and there are $$$p$$$ new elements which will still be distinct since we decreased them all by the same value. So, the number of distinct elements after the operation will be at least $$$\max (k - p, p)$$$. This number is at least $$$\lceil k / 2 \rceil$$$.
In each step choose a set containing numbers that in its binary representation have a $$$1$$$ in the $$$i$$$-th position and subtract $$$2^{i}$$$ from them. After $$$\left \lceil{\log_{2} n}\right \rceil$$$ steps we are done.