# Maximum value you can obtain at index 0 by performing given operation

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 < 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 < nums, Therefore nums + 1 and nums – 1. Now,  nums = 2, nums < nums, again repeat the step. Now nums 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 get increased and nums[i] get decreased. So, nums get increased by the amount (nums[i] – nums + 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, do the given operation
• Value at index 0 will get increased by the (nums[i] – nums +1) / 2
• Return the value at index 0 as the required answer.

Below is the implementation of the above approach:

## C++

 ` `  `#include ` `using` `namespace` `std;` ` `  `int` `maximumValue(vector<``int``>& nums, ``int` `n)` `{` `    ` `    ``int` `value_at_index_0 = nums;` ` `  `    ` `    ` `    ``sort(nums.begin() + 1, nums.end());` ` `  `    ` `    ``for` `(``int` `i = 1; i < n; i++) {` ` `  `        ` `        ` `        ` `        ``if` `(nums[i] > value_at_index_0) {` ` `  `            ` `            ``value_at_index_0` `                ``+= (nums[i] - value_at_index_0 + 1) / 2;` `        ``}` `    ``}` ` `  `    ` `    ``return` `value_at_index_0;` `}` ` `  `int` `main()` `{` `    ``vector<``int``> nums = { 1, 2, 3 };` `    ``int` `N = nums.size();` ` `  `    ` `    ``cout << maximumValue(nums, N);` ` `  `    ``return` `0;` `}`

Time Complexity: O(N * log N)
Auxiliary Space: O(1)

Related Articles: