Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and $B[i] \ge 1$.

I found the prime factors of $N$ and sorted them in decreasing order and if they are greater than $n$ then I divided them in $n$ groups optimally (minimizing the maximum product of a group). What can be the other approach since dividing in $n$ groups is NP-hard problem and I would like to get a better approach?

The approach fails sometimes. Like for N=384 and n=6 the best answer is

4 5 6 6 6 6



while this approach gives

4 5 5 5 6 7


  • $\begingroup$ What's the context in which you encountered this problem? Can you credit the original source for this problem? Also, do you require the entries of the array $B$ to be integers? $\endgroup$ – D.W. Jun 8 '18 at 18:47

Your Answer

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

Browse other questions tagged or ask your own question.