I was asked one coding question in interview, description was like below N factories are producing pollution. Given pollution amount in terms of integers. Count mini. no. of filters required to reduce total pollution by atleast half. One filter reduces pollution by half. and if you put another filter in same factory it will be 4th (N/2/2)

Example: N =[5,19,8,1]
totalPollution = 5 19 8 1=33

numberOfFiltersRequire =3

cause we can do something like this = [(19/2)/2, 8/2,5,1] = 4.75 4 5 1 = 14.75 which is less than half of existing pollution

 Example: N =[3,0,5]
  numberOfFiltersRequire =2

as we need to put filter in both polluting factory for this I wrote code like below

 int solve(int[] n){
    int count = 0;
    int totalPollution = Arrays.stream(n).sum();
    int halfPollution = totalPollution/2; //I know I should have taken double but thought int wold work
    long distinct =  Arrays.stream(n).distinct)().count();
    if(distinct == 1l)
     return  n; // this is the corner case where all factories pollute equally i.e [10,10]
  PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
  for(int a:n)
     pq.add(a);
   while(totalPollution >= halfPollution){
       int currnetPoll = pq.poll();
       int halfVal = currentPoll/2;
       totalPollution -= halfVal;
       count  ;
       pq.add(halfVal);
      
 }
 return count;
}

but strange to me it passed only sample test case but did not pass any other test cases for me, can anyone please help me how should I improve?

CodePudding user response：

Your programming logic seems ok. It is greedy algorithm. Use priority queue, remove the largest element every time reduce it by half and add it back to priority queue. Looks like you missed this:

Count mini. no. of filters required to reduce total pollution by atleast half.

Then following is wrong.

while(totalPollution >= halfPollution)

It has to be

while(totalPollution > halfPollution)

CodePudding user response：

You can sort the array in descending and divide each value by 2 till its lower than next value, increment counter each time you divide. Something like this:

    int solve(int[] n){
        int[] sortedArr = Arrays.stream(n).boxed().sorted(Comparator.reverseOrder())
                .mapToInt(Integer::intValue).toArray();

        if(sortedArr.length == 1)
            return 1;
        double prevNum = sortedArr[0];

        int total = Arrays.stream(sortedArr).sum();
        double requiredValue = (double) total/(double) 2;

        int countFilter = 0;
        for(int i=1; i<sortedArr.length; i  ){
            while (prevNum >= sortedArr[i] && total>requiredValue){
                //System.out.println(prevNum " " n[i] " " total " " countFilter);
                prevNum=prevNum/(double) 2;
                total-=prevNum;
                countFilter  ;
            }
        }
        return countFilter;
    }

CodePudding user response：

The greedy algorithm will work, but I'll mention that you can solve this in O(n) as well without too much extra effort. The idea is to split up the elements of arr into 'buckets' based on their highest set bit, and do operations on the entire highest-bit bucket at one time. The final step is a quickselect based algorithm that mimics the greedy algorithm, but allows us to avoid sorting.

1. Partition elements into m buckets according to their highest set bit (so 1 ceiling(log_2(max(arr))) buckets at most. For each bucket, also store its sum and the number of elements it contains.
2. Keep a total_reduction_still_needed variable, initialized as sum(arr)/2. Also keep a filters_used variable, initialized as 0. Since all our elements can be represented as binary fractions even after dividing by 2, you can even arithmetic left-shift all integers by m 1 to avoid having to use floating point math, but it's not strictly necessary.
3. While the sum of our highest bucket B, divided by 2, is less than or equal to total_reduction_still_needed: add the number of members of B to filters_used, subtract sum(B)/2 from the reduction still needed, and move all the elements of B to the second highest bucket, updating its sum and count.
4. Now, we have a highest bucket B whose sum is more than twice the reduction still needed. We need to find the smallest number of elements from the bucket that sum to at least a given number. Rather than sorting, we can do this in O(n) time using Quickselect median of medians with extra bookkeeping. This is a somewhat common technique but takes longer to explain; see for example this thread that gives pseudocode and an explanation.

The only part that requires a proof of O(n) time is the 'moving elements to the next highest bucket' step in (3). However, notice that putting two filters on each factory from the start gives an upper bound on the total number of filters needed, so we do at most 2n element moves here total (there's better upper bounds, but this is all that's needed for the proof).