Sunday, November 27, 2022
HomeSoftware DevelopmentReduce the max of Array by breaking array components at most Ok...

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


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

Examples:

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

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

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

Initilze begin with minimal attainable reply and finish with most attainable reply, then calculate the brink worth mid = (begin + finish) /2 and examine whether it is attainable to make each ingredient lower than or equals to mid in at most Ok 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 can retailer the reply
  • Whereas begin ≤ finish
    • Calculate mid = (begin + finish) / 2
    • Calculate the utmost variety of operations required to make each ingredient lower than or equal to mid.
    • Iterate over the given array
      • Test if the present ingredient is larger than mid
        • If true, then calculate the operation required to make this ingredient lower than or equals to mid
    • Test if the whole operation required to make each ingredient lower than or equal to mid is larger lower than equal to Ok
      • 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++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

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

{

    

    

    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.dimension(); i++) {

  

            

            

            

            

            

            if (arr[i] > mid) {

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

            }

        }

  

        

        

        

        

        

        

        if (operation <= Ok) {

            outcome = mid;

            finish = mid - 1;

        }

        else {

            begin = mid + 1;

        }

    }

  

    

    return outcome;

}

  

int foremost()

{

  

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

    int Ok = 4;

  

    

    cout << minimizeMaxElement(arr, Ok);

  

    return 0;

}

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments