How to solve equation with ceil function

274 Views Asked by At

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.

1

There are 1 best solutions below

4
On BEST ANSWER

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.