1802. Maximum Value at a Given Index in a Bounded Array

You are given three positive integers: n, index, and maxSum. You want to construct an array nums (0-indexed) that satisfies the following conditions:

The Five conditions

1. nums.length == n

The length of nums is equal to n.

2. nums[i] is a positive integer where 0 <= i < n.

Any value of array is positive integer. The range is from 0 to n.

3. abs(nums[i] - nums[i+1]) <= 1 where 0 <= i < n-1.

The different of ith and i+1th is less than or equal to 1.

• ith:how to pronounce?
• 小於等於
  • is less than or equal to
  • is no more than

4. The sum of all the elements of nums does not exceed maxSum.
5. nums[index] is maximized.

• 第 index number:how to pronounce?

Example

The inputs has 3 elements.

1. n: 4 
According to condition 1, The length of array is 4

2. index: 2
The range of index is from 0 to n-1.
And according to condition 5, index 2 is maximun in this case.

3. maxSum: 6
Sum of all the element should not exceed 6.

根據的不同用法：
1. according to Noun
2. based on
3. on the basis of

Solution

First, all the elements should be positive on the basis of condition 2. All the elements' minimun is 1, so maxSum should minus n. Now, get the possible maximun of the result(maxSum - n). But, the result still also cause that sum of all elements is larger than maxSum.
So, the program should iterate from (maxSum - n) to 1 until get the result which sould not exceed maxSum.
However if the test calculates from (maxSum - n) to 1, it will cosume O(n), choosing binary search which just consumes Ｏ(nlogn).

class Solution {
public:
  int maxValue(int n, int index, int maxSum) {
      int right = maxSum - (n -1);
      int left = 1, too_much = 0;
      double mid = left + ((right - left)/2),last_mid = 0;
      while (right>left){
        mid = left + ((right - left)/2);
        //cout <<"*** l:"<<left<<",r:"<<right<<",mid:"<<mid<<endl;
        if (mid == last_mid) {
          left++;
          mid = left + ((right - left)/2);
          //return mid;
        }
        int l_bottom = ((mid-index>1)?(mid-index):1);
        int l_num = ((mid-index>1)?index:(mid-1));
        //cout <<"l_bottom:"<<l_bottom<<",l_num:"<<l_num<<endl;
        if(index == 0)
            l_num = 0;
        int l_1 = ((mid-index>=1)?0:(index-mid)+1);
        double left_sum = ((mid - 1) + l_bottom) * l_num/2+ l_1;
        //cout <<"l_1:"<<l_1<<", l_s:"<<left_sum<<endl;;
        int r_num = (((mid-(n-index-1))>1)?((n-index-1)): mid-1);
        if(n-index == 1)
          r_num = 0;
        //cout <<"r_num:"<<r_num<<endl;
        int r_bottom = (((mid-(n-index-1))>1)?(mid-(n-index-1)):1);
        int r_1 =(((mid-(n-index-1))>=1)?0:(1-(mid-(n-index-1))));
        double right_sum = ((mid - 1) + r_bottom)* r_num /2 + r_1;
        //cout <<"r_b:"<<r_bottom<<",r_1:"<<r_1<<",r_s:"<<right_sum<<endl;
        if ((left_sum + right_sum + mid) > maxSum) {
            right= mid-1;
            too_much =1;
        } else if ((left_sum + right_sum + mid) < maxSum){
            left = mid;
            too_much =0;
        } else
            return mid;
        last_mid = mid;
        //cout <<"--- l:"<<left<<",r:"<<right<<",mid:"<<mid<<endl;
      }
      //cout <<"end"<<endl;
      return (too_much>0)?right:left;
  }
};

Explain binary search