| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
You are given an array , can perform two operations -if the size is greater than 1 choose two distinct elements and remove both of them -or remove a single element N — 10^5 , 1 <= arr[i] <= 10^9 Find the minimum operations to make array empty. TC — N=5, arr -> 1,2,2,3,5 Output -> 3 Explanation -> (1,2) (2,3) 5
What will be the approach of this ?
What is the minimum possible number of steps? When is this minimum possible?
Try focusing on the element/s with the highest frequency.
The minimum possible number of steps is $$$\lceil \frac{N}{2} \rceil$$$ — just keep removing pairs. Let's look at the element with highest frequency, and call this frequency $$$k$$$. Then this minimum is possible if and only if $$$k \leq N-k$$$. More intuitively, there should be at least as many "other" elements as there are of the current element. If this is the case, one greedy strategy that works is removing two of the most frequent numbers at each step.
If this is not the case, then we can remove at most one occurrence of the most frequent number at each step. For example, if the array is [1, 2, 3, 3, 3, 3], the best case solution is to remove an occurrence of 3 at each step ( (3, 1) (3, 2) (3) (3) ). This solution produces k steps.
suppose k < N — k , to remove these k elements (of highest frequency) we will need another k diff elements (which will be present in this case). After removal we will be left with N — 2*k elements.
My question is, for these remaining elements will it always be guaranteed that we can keep forming a pair of two distinct elements and thus make the arr empty in ceil [ (N-2*k)/2 ] moves ??
So if the condition is satisfied, you're right that the strategy of just removing that specific element may not always work. However, the strategy of removing the two most frequent elements at each step (not just the most frequent element at the start) will work. To prove this, we assume that we have used this strategy and it doesn't work — at the end we must have >2 of the same element, Then working backward, we can show that 1) that final element will be the most frequent element at every step, 2) every step therefore removed an occurrence of that element, so 3) the initial inequality $$$k \leq N-k$$$ was not satisfied, producing a contradiction.