Skip to content

Commit 7f5990a

Browse files
fishercoder1534fishercoder1534
committed
add 1300
1 parent b94da20 commit 7f5990a

File tree

3 files changed

+124
-0
lines changed

3 files changed

+124
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ _If you like this project, please leave me a star._ ★
99
| # | Title | Solutions | Video | Difficulty | Tag
1010
|-----|----------------|---------------|--------|-------------|-------------
1111
|1302|[Deepest Leaves Sum](https://leetcode.com/problems/deepest-leaves-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1302.java) | |Medium||
12+
|1300|[Sum of Mutated Array Closest to Target](https://leetcode.com/problems/sum-of-mutated-array-closest-to-target/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1300.java) | |Medium||
1213
|1299|[Replace Elements with Greatest Element on Right Side](https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1299.java) | |Easy||
1314
|1297|[Maximum Number of Occurrences of a Substring](https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1297.java) | |Medium||
1415
|1296|[Divide Array in Sets of K Consecutive Numbers](https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1296.java) | |Medium||

‎src/main/java/com/fishercoder/solutions/_1300.java

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package com.fishercoder.solutions;
2+
3+
/**
4+
* 1300. Sum of Mutated Array Closest to Target
5+
*
6+
* Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value,
7+
* the sum of the array gets as close as possible (in absolute difference) to target.
8+
* In case of a tie, return the minimum such integer.
9+
* Notice that the answer is not neccesarilly a number from arr.
10+
*
11+
* Example 1:
12+
* Input: arr = [4,9,3], target = 10
13+
* Output: 3
14+
* Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.
15+
*
16+
* Example 2:
17+
* Input: arr = [2,3,5], target = 10
18+
* Output: 5
19+
*
20+
* Example 3:
21+
* Input: arr = [60864,25176,27249,21296,20204], target = 56803
22+
* Output: 11361
23+
* */
24+
public class _1300 {
25+
public static class Solution1 {
26+
public int findBestValue(int[] arr, int target) {
27+
int ave = target / arr.length;
28+
int min = findMin(arr);
29+
int max = findMax(arr);
30+
//if ave is the best value, what's the difference to target?
31+
int closetDiff = findClosestDiffIfReplaceWithVal(arr, ave, target);
32+
int bestValue = ave;
33+
//extend candidate towards the right to see how close the sum could be to target
34+
int candidateOnTheRight = ave;
35+
while (candidateOnTheRight <= max) {
36+
int thisOne = findClosestDiffIfReplaceWithVal(arr, ++candidateOnTheRight, target);
37+
if (thisOne >= closetDiff) {
38+
break;
39+
} else {
40+
closetDiff = thisOne;
41+
bestValue = candidateOnTheRight;
42+
}
43+
}
44+
45+
//extend candidate towards the left to see how close the sum could be to target
46+
int candidateOnTheLeft = ave;
47+
while (candidateOnTheLeft >= min) {
48+
int thisOne = findClosestDiffIfReplaceWithVal(arr, --candidateOnTheLeft, target);
49+
if (thisOne >= closetDiff) {
50+
break;
51+
} else {
52+
closetDiff = thisOne;
53+
bestValue = candidateOnTheLeft;
54+
}
55+
}
56+
return bestValue;
57+
}
58+
59+
private int findClosestDiffIfReplaceWithVal(int[] arr, int replaceValue, int target) {
60+
int sum = 0;
61+
for (int i = 0; i < arr.length; i++) {
62+
if (arr[i] > replaceValue) {
63+
sum += replaceValue;
64+
} else {
65+
sum += arr[i];
66+
}
67+
}
68+
return Math.abs(sum - target);
69+
}
70+
71+
private int findMax(int[] arr) {
72+
int max = arr[0];
73+
for (int i = 1; i < arr.length; i++) {
74+
max = Math.max(max, arr[i]);
75+
}
76+
return max;
77+
}
78+
79+
private int findMin(int[] arr) {
80+
int min = arr[0];
81+
for (int i = 1; i < arr.length; i++) {
82+
min = Math.min(min, arr[i]);
83+
}
84+
return min;
85+
}
86+
}
87+
}

‎src/test/java/com/fishercoder/_1300Test.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1300;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import static org.junit.Assert.assertEquals;
8+
9+
public class _1300Test {
10+
private static _1300.Solution1 solution1;
11+
private static int[] arr;
12+
13+
@BeforeClass
14+
public static void setup() {
15+
solution1 = new _1300.Solution1();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
arr = new int[]{4, 9, 3};
21+
assertEquals(3, solution1.findBestValue(arr, 10));
22+
}
23+
24+
@Test
25+
public void test2() {
26+
arr = new int[]{2, 3, 5};
27+
assertEquals(5, solution1.findBestValue(arr, 10));
28+
}
29+
30+
@Test
31+
public void test3() {
32+
arr = new int[]{60864, 25176, 27249, 21296, 20204};
33+
assertEquals(11361, solution1.findBestValue(arr, 56803));
34+
}
35+
36+
}

0 commit comments

Comments
 (0)