Monday, December 31, 2018
805. Split Array With Same Average
class Solution {
public boolean splitArraySameAverage(int[] A) {
// for a previous i numbers in A [0, i)
// countB = m, countC = i - m
// B sumB C sumC
// We could have same
// For each coming A[i] -> we have 2 choices
// put into B -> sumB = sumB + A[i], countB = countB + 1, sumC = sumC, countC = countC
// put into C -> sumB = sumB, countB = countB, sumC = sumC + A[i], countC = countC + 1
// split into 2 groups -> avgB = sumB / countB, avgC = sumC / countC
// sumB / countB = sumC / countC -> sumB * countC = sumC * countB -> sumB * (count - countB) = (sum - sumB) * countB
// avg = avgB = avgC
// sumB * count = sum * countB -> sumC * count = sum * countC
int count = A.length;
int sum = 0;
for(int a : A) sum += a;
// Can we find a subset of A whose average equals to the average of A
// knapsack problem
}
}
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment