0

Let's say I have an array A whose sum % 6 = 3

My problem is to find a subarray such that if I remove that subarray then the remainder becomes 4

For example, if

A.sum % 6 = 3

I need to find subarray of A (sub(A)) such that

(A - sub(A)) % 6 = 4

The algorithm I have does this by storing the remainder for each element i and then looking for a subarray with remainder (3 - 4) % 6 = 5.

I am having trouble understanding how it works. How does taking the difference of remainders and then taking a modulo again by 6, give us the correct answer?

Umair Abid
  • 123
  • 4
  • First convert the mod operators into much more flexible congruence relations. Since congruences are *generalized equations* (equivalence relations) they enjoy well-known equational arithmetic,, e.g. here solving for $\,B_s = {\rm sub}(A)\,$ sum we get: $\bmod 6\!:\ \overbrace{A_s}^{\large 3}\! - B_s\equiv 4\iff B_s\equiv 3-4\equiv -1\equiv 5.\,$ See the linked dupes for more on congruence arithmetic. – Bill Dubuque Feb 06 '23 at 08:53

0 Answers0