Decrease the max of Array by breaking array components at most Ok occasions

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

Examples:

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

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

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

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

Observe the steps beneath to implement the above concept:

• Initialize a variable begin = 1 and finish = most potential 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 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 entire operation required to make each component lower than or equal to mid is bigger 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.

Time Complexity: O(log₂(max(arr)) * N), the place max(arr) is the utmost component and N is the dimensions of the given array.
Auxiliary House: O(1)