Reduce the max of Array by breaking array components at most Okay instances

[ad_1]

Given an integer array arr[] of measurement N and a constructive integer Okay, the duty is to reduce the utmost of the array by changing any aspect arr[i] into two constructive components (X, Y) at most Okay instances such that arr[i] = X + Y.

Examples:

Enter: arr = {9}, Okay = 2
Output: 3
Rationalization: Operation 1: Substitute aspect 9 into {6, 3} then array turns into {6, 3}.
Operation 2: Substitute aspect 6 into {3, 3} then array turns into {3, 3, 3}.
So, the utmost aspect in arr[] after acting at most Okay operations are 3.

Enter: arr = {2, 4, 8, 2}, Okay = 4
Output: 2

The issue will be solved utilizing binary search primarily based on the next concept:

Initilze begin with minimal attainable reply and finish with most attainable reply, then calculate the edge worth mid = (begin + finish) /2 and examine whether it is attainable to make each aspect lower than or equals to mid in at most Okay operations. Whether it is attainable, replace the outcome and shift finish of vary to mid – 1. In any other case, shift begin of vary to mid + 1.

Comply with the steps beneath to implement the above concept:

  • Initialize a variable begin = 1 and finish = most attainable reply.
  • Initialize a variable outcome that may retailer the reply
  • Whereas begin ≤ finish
    • Calculate mid = (begin + finish) / 2
    • Calculate the utmost variety of operations required to make each aspect lower than or equal to mid.
    • Iterate over the given array
      • Verify if the present aspect is bigger than mid
        • If true, then calculate the operation required to make this aspect lower than or equals to mid
    • Verify if the whole operation required to make each aspect lower than or equal to mid is bigger lower than equal to Okay
      • If true, replace the outcome and transfer the finish to mid – 1
      • In any other case, transfer the begin to mid + 1.
  • Return the outcome.

Beneath is the implementation of the above method.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int minimizeMaxElement(vector<int>& arr, int Okay)

{

    

    

    int begin = 1,

        finish = *max_element(arr.start(), arr.finish());

  

    

    

    int outcome = -1;

  

    

    whereas (begin <= finish) {

  

        

        int mid = (begin + finish) >> 1;

  

        

        

        

        

        int operation = 0;

  

        

        for (int i = 0; i < arr.measurement(); i++) {

  

            

            

            

            

            

            if (arr[i] > mid) {

                operation += ceil((double)arr[i] / mid) - 1;

            }

        }

  

        

        

        

        

        

        

        if (operation <= Okay) {

            outcome = mid;

            finish = mid - 1;

        }

        else {

            begin = mid + 1;

        }

    }

  

    

    return outcome;

}

  

int predominant()

{

  

    vector<int> arr = { 2, 4, 8, 2 };

    int Okay = 4;

  

    

    cout << minimizeMaxElement(arr, Okay);

  

    return 0;

}

Time Complexity: O(log2(max(arr)) * N), the place max(arr) is the utmost aspect and N is the scale of the given array.
Auxiliary Area: O(1)

[ad_2]

Leave a Reply