1
$\begingroup$

For a problem I came out with following equation: $$\left\lceil\frac{x_1}{k}\right\rceil + \left\lceil\frac{x_2}{k}\right\rceil + \left\lceil\frac{x_3}{k}\right\rceil + \cdots + \left\lceil\frac{x_n}{k}\right\rceil = v,$$

Here, $x_1, x_2, \cdots, x_n$ and $v$ are known. I need to find out the minimum value of $\boldsymbol{k}$ for which the above equation holds.

I tried using ceiling properties but not able to come up with any solution.

$\endgroup$
  • $\begingroup$ I'm not aure, but I think it depends on what the value of known constants are? It would be helpful if you gave us those values $\endgroup$ – KKZiomek Mar 8 '18 at 4:18
  • $\begingroup$ The values of constants are not fixed. I need to solve this equation for different set of (X, V) values. $\endgroup$ – quintin Mar 8 '18 at 4:23
1
$\begingroup$

I am assuming everything is positive here. For starters, you need $V$ to be less than or equal to the sum of the $X$s and greater than or equal to $n$. Now you can just do bisection with $k$ ranging from $1$ to the maximum of the $Xn$

Better, you can start by ignoring the ceiling functions, and get $k=\frac {\sum x_i}v$ as a lower bound. Each ceiling adds $1$ at the most, so $k'=\frac {\sum x_i}{v-n}$ is an upper bound.

$\endgroup$
  • $\begingroup$ This requires doing binary search for k between 1 and max(X). As, X can have a huge value and binary search might take time. Is there any faster method for this? $\endgroup$ – quintin Mar 8 '18 at 6:39
  • $\begingroup$ @BarryCipra: yes, I am. I'll add that. $\endgroup$ – Ross Millikan Mar 8 '18 at 15:29
  • $\begingroup$ This might be possible that v = n then how should we decide the upper bound? $\endgroup$ – quintin Mar 8 '18 at 19:14
  • 1
    $\begingroup$ If $v=n$ you just want all the fractions less than $1$ so any $k$ greater than all the $x_i$ will work. $\endgroup$ – Ross Millikan Mar 8 '18 at 19:19

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.