You are given an array of N integers where N <= 10^5 and arr[i] >= 1 and arr[i] <= 10^6. Each time you find the sum of all the elements in the array, divide it by 2 and take the floor value. The number which is closest to this value is removed from the array, in case of tie the number with lowest id is removed. The process continues until there is single element in the array. Find the single element. The array can have duplicates.
How to solve this problem in the given time constraints. Brute force will be O(n^2)
Example :
N = 4 arr[] = 1 3 5 7
Output = 5
in first step, sum = 16, its half = 8, closest to it = 7, remove 7, now the array is 1 3 5
in second step, sum = 9, its half = 4, closest to it is 3 and 5, 3 is with lowest id, remove it, now array is 1 5
in second step, sum = 6, its half = 3, remove 1. final array is 5.
There were 3 problems, one was valid bracket sequence, other was in out dp but n was 1000 so it can be solved with normal dfs too in N^2. this was the last problem
if 7 is removed in the first step then how the final array contains 7 ?
u can always remove only the maximal or 2-nd maximal element => it will be O(n log n) solution
I over complicate it. Thanks for help. feeling bad :(
u can easy write it without complex structures, using only vector : sort elements, and u can remove only last or last but one element by O(1). But it would be O(n log n) if u using qsort, or O(N) if u use counting sort
how to know which one is remove..
u can keep the sum of array, and honestly calculate which one is closer
Can you prove this? I mean why would the removed element will be either max or 2nd max always?
$$$\displaystyle$$$ Quite straightforward to prove:
Assuming $$$N\geq2$$$ and the list $$$a$$$ is sorted in non-decreasing order, then:
$$$\frac{\sum_{i=1}^{N}a_i}{2} = \frac{a_{N-1} + a_N}{2} + \frac{\sum_{i=1}^{N-2}a_i}{2} \geq \frac{a_{N-1} + a_N}{2} \geq a_{N-1}$$$
Hence it wouldn't ever be closer to anything smaller than $$$a_{N-1}$$$
@Enchom thanks..
Enchom How do you prove that it is a tight bound? Based on similar arguments you used, even the following thing holds:
But that's not a tight bound.
This maybe a noob question, but I am not able to get it.
Well, if you want to prove that "the chosen value is always the largest or the second largest", then you don't need any proof of it being a tight bound.
By the same logic, your statement correctly proves "the chosen value is always the largest, second largest or the third largest".
Once I've proven that the formula yields a value larger than $$$a_{n-1}$$$ it is clear that the chosen value can never be anything smaller than $$$a_{n-1}$$$, since $$$a_{n-1}$$$ itself would then be a not-worse pick.
If you really want to have a tight bound then the only way to make it tighter is to try and prove that it is always the maximum that is chosen, but that is not true. Easiest way to show that is via an example:
Consider the sequence "1 2"
We compute the value $$$\lfloor\frac{1+2}{2}\rfloor=1$$$ which is closer to 1 than to 2. Hence, it is not guaranteed that the largest one is always removed, and considering only the largest two elements is a tight bound on the number of elements you need to consider.
I think following algo should work .
1. put all the values in a multiset .
2 .Find the sum of the whole array .
3 .Find the lower (I mean you have to find just smaller or equal element) and upper bound of sum/2 .
4 .Remove that element which absolute difference is minimum and subtract that element from sum .
5 .Do steps 3 and 4 until there is only one element in the array .
UPD : The time complexity will be nlog(n) .