mkagenius's blog

Bytecode2012- The wild wizard, my approach, is it correct?
By mkagenius, 13 years ago, In English

Here is the problem statement- if u can login — https://bytecode.interviewstreet.com/challenges/dashboard/#problem/4f497b0018bad

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks. :D

    a small question, will it be F[(A[i] - k + mod) % mod] ?

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Yes, you are right. There is some bugs in the above code, but you understand main idea.

      → Reply