If we are given a number k (1 <= k <= 4) and two numbers S (1 <= S <= 1000 ) and P (1 <= P <= 1000), we have to find a sequence of k numbers such that, the sum of all elements in the sequence is S and their product is P. Print NO if the sequence does not exist and print the sequence otherwise.
We can brute-force all the cases as k is very small,
1 2 3 4 5 6 7 8
if k == 1
then do ...
if k == 2
then do ...
if k == 3
then do ...
if k == 4
then do ...
For cases 1 and 2 it is very easy to find the sequence.
But i have no idea how we find it for k = 3 and k = 4.
Please help me to solve this problem.
Pretty much, although I'm not sure I'd be so eager to discard the range (sqrt(P);P]. I'm not saying it's wrong, just that I'm not entirely sure it's correct.
Let F( M, K, S, P ) be a set of K integers >= M, with sum == S and product == P
Specific problem: Find F( 1, K, S, P )
General problem: find F( M, K, S, P ):
1. if M > (S-K+1) or M > P there is no solution
2. let the smallest number >= M that divides P be x
3. find F( x+1, K-1, S-x, P/x )
4a. if found, [x] union F( x+1, K-1, S-x, P/x ) is the solution
4b. else find F( x+1, K, S, P )