_1300.java

packagecom.fishercoder.solutions.secondthousand;

publicclass_1300 {
publicstaticclassSolution1 {
publicintfindBestValue(int[] arr, inttarget) {
intave = target / arr.length;
intmax = arr[0];
intmin = arr[0];
for (inti = 1; i < arr.length; i++) {
min = Math.min(min, arr[i]);
max = Math.max(max, arr[i]);
 }
if (ave >= max) {
returnmax;
 }
// if ave is the best value, what's the difference to target?
intclosetDiff = findClosestDiffIfReplaceWithVal(arr, ave, target);
intbestValue = ave;
// extend candidate towards the right to see how close the sum could be to target
intcandidateOnTheRight = ave;
while (candidateOnTheRight <= max) {
intthisOne = findClosestDiffIfReplaceWithVal(arr, ++candidateOnTheRight, target);
if (thisOne >= closetDiff) {
break;
 } else {
closetDiff = thisOne;
bestValue = candidateOnTheRight;
 }
 }

// extend candidate towards the left to see how close the sum could be to target
intcandidateOnTheLeft = ave;
while (candidateOnTheLeft >= min) {
intthisOne = findClosestDiffIfReplaceWithVal(arr, --candidateOnTheLeft, target);
if (thisOne >= closetDiff) {
break;
 } else {
closetDiff = thisOne;
bestValue = candidateOnTheLeft;
 }
 }
returnbestValue;
 }

privateintfindClosestDiffIfReplaceWithVal(int[] arr, intreplaceValue, inttarget) {
intsum = 0;
for (inti = 0; i < arr.length; i++) {
if (arr[i] > replaceValue) {
sum += replaceValue;
 } else {
sum += arr[i];
 }
 }
returnMath.abs(sum - target);
 }
 }
}