Matching sums of consecutive elements of two sets

Question

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!

"at the same starting and ending positions in the two sets" Cool, gotcha. "including overlapping subsets?" Overlapping. What? If they have the same start and end positions, what is overlapping what? Can you explain that aspect in more detail with an example? — Idle_Mind
– Idle_Mind, Commented Apr 5, 2022 at 20:07
At first glance this is just a set of brute force nested for loops generating all the possible start/end positions. — Idle_Mind
– Idle_Mind, Commented Apr 5, 2022 at 20:09
Probably also at second glance, since this is inherently a quadratic problem (if we don't try to get fancy with exploiting properties of primes and composites and just assume arbitrary lists). Hint: for (int i = 0; i < P.Length; ++i) { int sum_P = P[i]; int sum_C = C[i]; for (int j = 1; j < P.Length - i; ++j) { ...} }. — Jeroen Mostert
– Jeroen Mostert, Commented Apr 5, 2022 at 20:16
Overlapping matching subsets can either be nested as in the given example or their starting index is before the ending index of the previous matching two subsets. — Ali Adams
– Ali Adams, Commented Apr 5, 2022 at 20:18

Idle_Mind · Accepted Answer · 2022-04-05 20:22:49Z

1

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

answered Apr 5, 2022 at 20:22

Idle_Mind

39.3k3 gold badges31 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ali Adams Over a year ago

Too slow for a 10,000 numbers.Any optimization please as I need to do it for 1000000 primes and composites. Perhaps there are no more than these two matching subsets (53 and 31) because prime numbers increase much fasters than composite numbers.

Ali Adams Over a year ago

You will love these twin numbers 😊 QuranCode.com/506Paper.pdf

Collectives™ on Stack Overflow

Matching sums of consecutive elements of two sets

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related