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
    Commented Dec 15, 2020 at 5:46
  • $\begingroup$ @saulspatz Edited. $\endgroup$
    – Anonymous
    Commented Dec 15, 2020 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
    Commented Dec 22, 2020 at 11:01
  • $\begingroup$ @Servaes Just one. $\endgroup$
    – Anonymous
    Commented Dec 23, 2020 at 18:45

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .