Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Decrease the max of Array by breaking array parts at most Okay instances

[ad_1]

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

Examples:

Enter: arr = {9}, Okay = 2
Output: 3
Clarification: Operation 1: Change component 9 into {6, 3} then array turns into {6, 3}.
Operation 2: Change component 6 into {3, 3} then array turns into {3, 3, 3}.
So, the utmost component 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 thought:

Initilze begin with minimal potential reply and finish with most potential reply, then calculate the edge worth mid = (begin + finish) /2 and verify whether it is potential to make each component lower than or equals to mid in at most Okay operations. Whether it is potential, replace the consequence 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 thought:

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

Beneath is the implementation of the above strategy.

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 consequence = -1;

  

    

    whereas (begin <= finish) {

  

        

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

  

        

        

        

        

        int operation = 0;

  

        

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

  

            

            

            

            

            

            if (arr[i] > mid) {

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

            }

        }

  

        

        

        

        

        

        

        if (operation <= Okay) {

            consequence = mid;

            finish = mid - 1;

        }

        else {

            begin = mid + 1;

        }

    }

  

    

    return consequence;

}

  

int fundamental()

{

  

    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 component and N is the scale of the given array.
Auxiliary House: O(1)

[ad_2]

Leave a Reply