### ikbal's blog

By ikbal, 10 years ago,

statement

Problem is actually asks calculate number of partitons of n.

Is there anyone knows something better then O(n^2) approach?

UPD: Thank you for O(n sqrt(n)) solution fchirica , but i need proof too.

• +8

 » 10 years ago, # | ← Rev. 2 →   +29 I know an O(n * sqrt(n)) approach, but I don't know its proof. I think proving it is difficult, so just take it as magic :)Let P(n) = number of partitions of n.Then, P(n) = P(N — 1) + P(N — 2) — P(N — 5) — P(N — 7) + ...The k-th term of sum in absolute value is P(N — x[k]). The signs of sum's terms alternate from 2 to 2, so they are ++--++--++-- and so on. By x[k] I noted k-th pentagonal number . By formula of pentagonal numbers it's easy to see that when calculating P(n) you add about sqrt(n) numbers (because there are about sqrt(n) pentagonal numbers <= n) so complexity is O(n * sqrt(n)).
•  » » 10 years ago, # ^ |   0 Well, proving it is reading the Wikipedia article on pentagonal numbers :D Aside from that, an approach should pass comfortably.