# How to find the numbers efficiently given their sum and product?

Problem Statement: This is a rather simple problem to describe. You will be given three numbers $$S,P$$ and $$k$$. Your task is to find if there are integers $$n_1,n_2,\dots,n_k$$ such that $$n_1+n_2+\dots+n_k=S$$, and $$n_1 n_2\dots n_k=P$$.
If such integers exist, print them out. If no such sequence of integers exist, then print "NO".

For example if $$S=11,P=48$$, and $$k=3$$ then $$(3,4,4)$$ is a solution. On the other hand, if $$S=11,P=100$$ and $$k=3$$, there is no solution and you should print "NO".

Given that, $$1\leq k \leq 4$$, $$1 \leq S \leq 1000$$ and $$1\leq P \leq 1000$$.

My Approach: $$n_1,n_2,\dots,n_k$$ have to satisfy two conditions: $$n_1+n_2+\dots+n_k=S$$, and $$n_1 n_2\dots n_k=P$$.
The second condition implies that $$n_i$$ is a divisor of $$P$$ for all valid $$i$$, hence we can narrow down the search using this fact**. So I factored the number $$P$$ and stored its divisors. Next I implemented a recursive solution to fill each variable and solve the sub problem with one less variable to fill each time. I did this only for $$k-1$$ variables as the $$k$$-th variable is fixed automatically by the first condition.

** I came to this conclusion because I found that any number less than or equal to $$1000$$ has at most $$32$$ divisors (for reference https://www.geeksforgeeks.org/querying-maximum-number-divisors-number-given-range/), which means a total of $$64$$ (taking both the negative as well as positive divisors as the problem only says integers and not positive integers) resulting in a total of $$64^4 = 16777216$$ possibilities which can easily be searched through in time.

I did get an "AC" (i.e. the solution passed all the test cases (using only the positive numbers, though nothing like "only positive integers" was mentioned)).

But I just wanted to know that can we do better, and find the solution more efficiently, because this approach will take up a lot of time with more number of variables. Is there any other way to solve this problem in that case?

• Please try to make your questions self-contained. I know I don't want to have to click through links just to find out what your question is, and I doubt may other people do. Dec 15 '20 at 5:46
• @saulspatz Edited. Dec 15 '20 at 6:06
• Should your program print all solutions, or just one? For example, for $(S,P,k)=(30,840,3)$ there are the distinct solutions $(7,8,15)$ and $(6,10,14)$. Dec 22 '20 at 11:01
• @Servaes Just one. Dec 23 '20 at 18:45

I'm not sure I understand exactly what you did, but limiting the possibilities to the factors of $$P$$ must be the most important step. The biggest any single summand can be is $$S-(k-1)$$ which may allow one to substantially cut down on the possibilities. In the example, $$S=11, P=100, k=3$$ this observation immediately limits the possible $$n_i$$ to $$1,2,4,5$$.
You also may be able to cut the process short. When you find out that you can't do it if $$n_3=5$$, you can note that the largest product you can make is $$4^3=64<100$$ and so it's impossible.