### Manish-Kumar's blog

By Manish-Kumar22 months ago, ,

otherwise — http://pastebin.ca/2121976

My approach,

Make a cumulative sum array.

Now for every index starting from 0, do binary search for k, k+mod, k + 2*mod, ..., k + 76*mod on range limited by previous max-length found, i.e. if we already have found an array of length L, which sum upto k (after doing mod) , then accordingly we have to modify the binary-search space, because we do not require a shorter-length answer.

Will this approach time-out ? As I can't submit there anymore, I need your help to see whether it is correct approach or not.

 » 22 months ago, # | ← Rev. 2 →   +2 There is solution for O(max(n, m)) 1. Make a cumulative sum array. A 2. Make an array `FirstTimeOccurence[0..m-1], F[i] = -1` ``````for (int i = 0; i < n; i++) { A[i] %= mod; if (F[(k - A[i] + mod) % mod] != -1) // check subarray (F[(k - A[i] + mod) % mod], i) if (F[A[i]] == -1) F[A[i]] = i; } ``````"Beware of bugs in the above code; I have only proved it correct, not tried it." (c) Donald Knuth
•
 » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Thanks. `:D`a small question, will it be `F[(A[i] - k + mod) % mod]` ?
•
 » » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 Yes, you are right. There is some bugs in the above code, but you understand main idea.