codeedoc's blog

Hi! I need a little help with a problem .
By codeedoc, 5 years ago, In English

this should be a classical problem: We have a group of numbers named A with the size of n. Does A have a subgroup such that the sum of it is divisible by m?
m,n>=10^5

I couldn't find any solution with an order better than O(n*m).

thanks for helping :)

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a randomized tilde-O(n+m) solution for prime m out there, but I'm not sure if it's feasible with your constraints since its constants are fairly high. I'm pretty sure there's a way to adapt the solution to non-prime m, though I haven't spent too much time trying to do so.

→ Reply