### DrinkWaterEatFood's blog

By DrinkWaterEatFood, history, 5 years ago,

Recently I encountered the following problem in the recruitment test for IBM research.

There is an array of size K with elements from 1 to N and an array of size N with elements from 1 to K. Prove that there exists a sub-array of the first array and a sub-array of the second array with the same sum.

I was thinking of applying pigeonhole principle using difference of prefix sums but could not get anything concrete. Any ideas about how to prove this ?

• +39

 » 5 years ago, # | ← Rev. 2 →   -38 both of them have a sub-array of sum 1EDIT: just removed an annoyingly large image
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 There isn't every element presented neccesarily. If N=2, K=5, then arrays can be e.g. {2,2,2,2,2} and {3,5}.
•  » » » 5 years ago, # ^ |   0 ohin my defense it wasn't very clearly stated... though I should've figured :face_palm:
 » 5 years ago, # |   +37 Nice problem. It is quite not straightforward, so no shame if you can't solve it. Not going to burn the IBM interview question though, because it is hard to find nice problems like this. Usually interviewers give hints for such hard problems or don't expect the candidate to fully solve it, looking at approaches the candidate tries to use.
 » 5 years ago, # |   +15
•  » » 5 years ago, # ^ |   0 Thank you. Such clever uses of the pigeonhole principle never fail to amaze me.