We all know that the number of solutions to a+b = 3 (where a and b are non negative) can be easily found out by stars and bars theorem. So answer of the above is 4. { (3,0),(0,3),(1,2),(2,1)}. But I want the answer to be 2 as the first two and last two are equivalent. Formally, as the stars and bars give the number of ordered sets, I want to find out the number of unordered sets.
Number of ordered sets ((a+b)/2)+1 if i understood your question correctly.
This can be solved by dynamic programming the general case. First of all define P(N,K) as the number of ways you can represent N using K numbers in ascending order.
Now for solving P(N,K), if K > N then answer is 0, otherwise let's distribute 1 item on each set. Your task is now to distribute N — K items without breaking the ascending order.
If you place an item, in the ith set, you must use n — i — 1 items for later sets to compensate. So you can just apply dynamic programming and solve it O(N*K).
N is up to 1e9. Can we use prime factors of N to solve this?
Can you post the problem link?
?detaR tI sI
I'm gonna take a guess and say that you are looking for the partitions of a number. https://en.wikipedia.org/wiki/Partition_(number_theory) You can check here for fancy formulae, or just look for a dp solution :)