CPharderthanDarkSouls's blog

By CPharderthanDarkSouls, history, 2 years ago, In English

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 ?

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Hint 1
Hint 2
Solution
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Then this minimum is possible if and only if k≤N−k. More intuitively, there

    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 ??

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.