1
// This Question Includes Both Binary Search And bit of Greedy Concept also.
2
// See We Know Ans Always Lies Between 0 and maximum element according to given
3
// question condition Because sum value at maximum element is same as any other
4
// element greater than it. So we get our sum from getval function after that
5
// you need to choose as to move forward(l = mid+1) or backward i.e.(h = mid-1)
6
// so if sum value we obtain is less than target then l = mid+1 why so?? Because
7
// 2 3 5 lets suppose you are having this array if we pick 2 as mid then sum
8
// value will be 6 whereas if we pick 3 then sum value will be 8 and 10 when we
9
// pick 5 so notice that sum will increase when we increase value and
10
// correspondingly decrease when we decrease value...So yess This is all what we
11
// did and got Accepted.
12
class Solution {
13
 public:
14
  int getval(int mid, vector<int> &arr) {
15
    int sum = 0;
16
    for (int i = 0; i < arr.size(); i++) {
17
      if (arr[i] > mid)
18
        sum += mid;
19
      else
20
        sum += arr[i];
21
    }
22
    return sum;
23
  }
24
  int findBestValue(vector<int> &arr, int target) {
25
    int n = arr.size();
26
    int l = 0, h = *max_element(arr.begin(), arr.end());
27
    int ans = 0, min1 = INT_MAX;
28
    while (l <= h) {
29
      int mid = l + (h - l) / 2;
30
      int k = getval(mid, arr);
31
      if (k == target) {
32
        return mid;
33
      } else if (k < target) {
34
        l = mid + 1;
35
      } else
36
        h = mid - 1;
37

38
      int j = abs(k - target);
39
      if (j < min1) {
40
        min1 = j;
41
        ans = mid;
42
      } else if (j == min1) {
43
        ans = min(ans, mid);
44
      }
45
    }
46
    return ans;
47
  }
48
};