9
$\begingroup$

Given an array A of size n with elements from 1 to k and another Array B of size k with elements 1 to n. Show that they have a subarray of the same sum where n,k >= 1.

So far I have done this much analysis:

Define d = P1- P2 where P1 and P2 are prefixes of array A and B. For some subarrays in A and B to have common sum d should be same for at least 2 pairs(P1, P2) and possible pairs are (n+1)(k+1) and d can have values from -nk to nk i.e. 2nk + 1 differences.

How should I proceed further? or is there any another way(Induction or something different) of proving the same?

$\endgroup$
  • $\begingroup$ Presumably you mean non empty not-necessarily contiguous subarray? $\endgroup$ – DanielV Oct 26 '17 at 16:39
  • $\begingroup$ Non-empty and contiguous(necessarily). Subsequence(non-empty subset) case is trivial. @DanielV $\endgroup$ – Kunal Vallecha Oct 26 '17 at 17:54
  • $\begingroup$ @PrakharAgarwal: You suggested an edit replacing the first instance of "subarray" by "subsequence". This edit was rejected. It would have made the post inconsistent (as the term "subarray" is used again further down), and it clearly conflicts with the author's intent, judging from the above comment. If you're interested in the subsequence case (as your bounty offer in connection with your suggested edit might indicate), you can ask a separate question about that. $\endgroup$ – joriki Jun 21 '18 at 5:43
  • $\begingroup$ @joriki Well, Agarwal already asked a PSQ about that. $\endgroup$ – Saad Jun 21 '18 at 9:22
  • $\begingroup$ This is a slight generalization of this problem: math.stackexchange.com/questions/2776479/… . $\endgroup$ – mjqxxxx Jun 27 '18 at 2:00
4
+50
$\begingroup$

Assume w.l.o.g. that $\sum_{i=1}^n A_i\leq \sum_{j=1}^k B_j$. Then for every prefix $P_A$ of $A$, there is a prefix $P_B$ of $B$ such that $0\leq S(P_A) - S(P_B) < n$, where by $S(P_A)$ and $S(P_B)$ I mean sums of those prefices. Since there are $n+1$ prefices of $A$, for two of them, those differences must be the same, and it gives us subarrays of equal sums.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.