1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – saulspatz
    Dec 15 '20 at 5:46
  • $\begingroup$ @saulspatz Edited. $\endgroup$
    – Anonymous
    Dec 15 '20 at 6:06
  • $\begingroup$ 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)$. $\endgroup$
    – Servaes
    Dec 22 '20 at 11:01
  • $\begingroup$ @Servaes Just one. $\endgroup$
    – Anonymous
    Dec 23 '20 at 18:45
1
$\begingroup$

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.

No doubt there are other observations one can make, but you probably reach the point of diminishing returns quickly.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.