Medium
You are given an integer array nums
.
Split nums
into two arrays A
and B
using the following rule:
nums
must go into array A
.B
.Return the absolute difference between the sums of the two arrays: |sum(A) - sum(B)|
.
Note: An empty array has a sum of 0.
Example 1:
Input: nums = [2,3,4]
Output: 1
Explanation:
nums[2] = 4
is placed in array A
.nums[0] = 2
and nums[1] = 3
are placed in array B
.sum(A) = 4
, sum(B) = 2 + 3 = 5
.|4 - 5| = 1
.Example 2:
Input: nums = [-1,5,7,0]
Output: 3
Explanation:
nums[2] = 7
and nums[3] = 0
are placed in array A
.nums[0] = -1
and nums[1] = 5
are placed in array B
.sum(A) = 7 + 0 = 7
, sum(B) = -1 + 5 = 4
.|7 - 4| = 3
.Constraints:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
public class Solution {
public long splitArray(int[] nums) {
int n = nums.length;
boolean[] isPrime = sieve(n);
long sumA = 0;
long sumB = 0;
for (int i = 0; i < n; i++) {
if (isPrime[i]) {
sumA += nums[i];
} else {
sumB += nums[i];
}
}
return Math.abs(sumA - sumB);
}
// Sieve of Eratosthenes to find all prime indices up to n
private boolean[] sieve(int n) {
boolean[] isPrime = new boolean[n];
if (n > 2) {
isPrime[2] = true;
}
for (int i = 3; i < n; i += 2) {
isPrime[i] = true;
}
if (n > 2) {
isPrime[2] = true;
}
for (int i = 3; i * i < n; i += 2) {
if (isPrime[i]) {
for (int j = i * i; j < n; j += i * 2) {
isPrime[j] = false;
}
}
}
isPrime[0] = false;
if (n > 1) {
isPrime[1] = false;
}
return isPrime;
}
}