Given two sets of integers P and C of the same length. How can I find ALL matching sums of consecutive elements at the same starting and ending positions in the two sets, including overlapping subsets?
C# is preferred but non-Linq please.
Example:
Let P and C be the sets of the first ten prime and composite numbers:
P = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }
C = { 4, 6, 8, 9, 10, 12, 14, 15, 16, 18 }
Match 1: [index starts at 0]
SumP[3..5] = 7 + 11 + 13 = 31
SumC[3..5] = 9 + 10 + 12 = 31
Match 2: [index starts at 0]
SumP[2, 6] = 5 + 7 + 11 + 13 + 17 = 53
SumC[2, 6] = 8 + 9 + 10 + 12 + 14 = 53
I need to find if the above two sums are the only ones or not!
Here's the brute force approach with nested for loops, ignoring the "overlapping" part which I don't understand yet:
for(int indexA=0; indexA<P.Length; indexA++) {
for(int indexB=indexA; indexB<P.Length; indexB++) {
int sumA = 0, sumB = 0;
for(int i=indexA; i<=indexB; i++) {
sumA += P[i];
sumB += C[i];
}
if (sumA == sumB) {
Console.WriteLine("[" + indexA + ", " + indexB + "] : Sum = " + sumA);
}
}
}
Output:
[2, 6] : Sum = 53
[3, 5] : Sum = 31