Given an array nums[] of size N, Find the maximum value you can achieve at index 0 after performing the operation where in each operation increase the value at index 0 by 1 and decrease the value at index i by 1 such that nums[0] < nums[i] (1 ≤ i ≤ N-1). You can perform as many moves as you would like (possibly, zero).
Examples:
Input: nums[] = {1, 2, 3}
Output: 3
Explanation: nums[0] < nums[1], Therefore nums[0] + 1 and nums[1] – 1. Now, nums[0] = 2, nums[0] < nums[2], again repeat the step. Now nums[0] becomes 3 which is the maximum possible value we can get at index 0.Input: nums[] = {1, 2, 2}
Output: 2
Approach: The problem can be solved based on the following idea:
In order to achieve maximum value at index 0, sort the array from index 1 to the last index and can also start iterating it from index 1 and if at any point nums[i] is found to be greater than the element present at index 0, according to the given operation nums[0] get increased and nums[i] get decreased. So, nums[0] get increased by the amount (nums[i] – nums[0] + 1) / 2 when encountered with a greater value.
Follow the steps mentioned below to implement the idea:
- Store the initial value present at index 0 in a variable.
- Sort the array from index 1 to the last index.
- Iterate from index 1 and if found nums[i] > nums[0], do the given operation
- Value at index 0 will get increased by the (nums[i] – nums[0] +1) / 2
- Return the value at index 0 as the required answer.
Below is the implementation of the above approach:
C++
|
|
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Related Articles: