2
$\begingroup$

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

since

(4-(1-1))*(5-(2-1))*(6-(3-1))*(6-(4-1))*(6-(5-1))*(6-(6-1))=384

while this approach gives

4 5 5 5 6 7

since

(4-(1-1))*(5-(2-1))*(5-(3-1))*(5-(4-1))*(6-(5-1))*(7-(6-1))=384
$\endgroup$
1
  • $\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.