deque<int> dq;
// insert all the elements in dq
for(int i = 1; i <= N; ++i)
dq.push_back(i);
while(dq.size() > 2) {
// remove the killer
int killer = dq.front();
dq.pop_front();
// remove the one who is spared
int spared = dq.front();
dq.pop_front();
// remove the person to be killed
dq.pop_front();
// insert killer and spared at their right positions
dq.push_back(killer);
dq.push_front(spared);
}
vector<int> result;
for(auto num : dq)
result.push_back(dq);
sort(result.begin(), result.end());
return result;
Sure the 2nd question was that we had to pick any 3 elements from an array discard the maximum and minimum and keep the middle back so we need to tell how many maximum distinct elements we can end up with?
And 4th was we have an operation del(l,r) l<=r which deletes a[l],a[l+1]…a[r] to make array non-decreasing so we need to tell all possible count of such del(l,r) for an array
Question 2-
Remove minimum number of elements to make array with all numbers distinct. You select any 3 elements and remove the largest and smallest element from the array while retaining the mid one. For ex- let numbers be 1 1 2 3 4, then you pick 1 1 and 2, remove 1 and 2 and retain 1, so final array looks like 1 3 4. You have to get the final array with as distinct elements as possible.
Solution-
This question was all about observation. Each number in the array obviously has either odd or even frequency. Let’s handle both the cases.
Odd(and > 1)-
If the frequency of number is > 1 and odd, we repeatedly pick 3 instances of it and remove 2 of them(the smaller and the larger). So, in each round it’s frequency reduces by two. For ex- let there be 5 instances of 1- 1 1 1 1 1.
After first round of only 3 instances are left, and after the second round only instance of 1 is left. And we are done here, we successfully eliminated all the duplicates.
Thus, for any number with frequency > 1 and odd, we can safely remove all it’s duplicates without having to remove anything extra.
Even Frequency -
This part is little tricky, let’s suppose for the simplicity we have frequency > 2, i.e. 4, 6, … and so on. We can start doing the same thing we did in the last step. We pick three instances of it and remove two of them and repeat the process. At last, we will be left with only 2 instances of it. So, what to do from here? We can not proceed any further. Think about it?
Answer
Suppose there is one other such number who has even frequency(= 2, if it is not equal to 2, we can use the same process and reduce it to 2). Let’s say for example - 2 2 4 5 1 3 3.
You can see that 2 and 3 appear two times. So, what we can do is that pick 2 instances of either of them and 1 of the other and do the elimination. Let’s say we pick 2, 2 and 3. So after elimination one instance of 2 and one instances of 3 is removed. And our array now reduces to 2 4 5 1 3.
Bingo!
This helps us reach an important conclusion - we can pair numbers with even frequency and remove duplicates.
But what if there is no pair of numbers with even frequency? Such as in 2 2 3 4 5 or in 2 2 3 3 4 5 5. In the later case, 5 can not be paired with any other number with even frequency as 2 and 3 already makes a pair and 4 has an odd frequency?
In such a case, we have no other option but to remove one extra element. For example, the above arrays can be reduced to 2 4 5 and 2 3 5(these are only one such way and ofcourse there can be other ways).
So, to summarize-
Summary
Count the number of numbers with an odd frequency, let say their count is O.
Count the number of numbers with an even frequency, let say their count is E.
If E is even, then the answer will be O + E, otherwise it would be O + E - 1.
