## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Implement a ceil() function

Sharing is caring!

In this post I will explain a less intuitive approach of implementing a ceil() function in Java, that is faster than known comparison approaches.

A few known facts
Fact 1
Dividing two integers $a$ and $b$ in Java will always floor the result:

int a, b;
int ans = a/b; // is the same as Math.floor(a/b)


well almost. Actually Math.floor(a/b) rounds towards negative infinity, where as a/b rounds towards zero:

System.out.println(Math.floor(-1.5)); // -2
System.out.println(-3/2); // -1


Fact 2
$\lfloor x \rfloor = m$ if $m \le x \textless m+1$
$\lceil x \rceil = n$ if $n - 1 \textless x \le n$

Fact 3
$\lfloor x \rfloor \le \lceil x \rceil$

What we need is $\lfloor (x + s) \rfloor == \lceil x \rceil$
Since dividing two integers $a$ and $b$ in Java will always floor the result, we need to find some $s$ such that $\lfloor (x + s) \rfloor == \lceil x \rceil$.

How do we find $s$?
Think about it this way: $\lceil \frac{a}{b} \rceil \textgreater \lfloor \frac{a}{b} \rfloor$, except when $\frac{a}{b}$ is a whole number. So, we want to bump $\frac{a}{b}$ to (or past) the next whole number, unless $\frac{a}{b}$ is a whole number, by adding $s$. This way $\lfloor \frac{a}{b} + s \rfloor == \lceil \frac{a}{b} \rceil$. We want to find $s$ so that for whole numbers, it won’t quite push them up to the next whole number, but for non-whole numbers it will.

For instance, assume $a=6, b=3$ and $s=1$ then $\lfloor \frac{a}{b} + s \rfloor = \lfloor \frac{6}{3} + 1 \rfloor = 3 \ne \lceil \frac{a}{b} \rceil = \lceil \frac{6}{3} \rceil = 2$, which is not the desired result. As you can see, by using $s=1$ we bumped $\frac{a}{b}$ to far. So $s$ must definitely be less than $1$.

So how much $s$ is just enough?

Assume $a=7, b=3$. Then $\frac{a}{b} = \frac{7}{3}$, which can be re-written as:
$\frac{7}{3} = \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} + \frac{1}{b} = (\frac{1}{3} + \frac{1}{3} + \frac{1}{3}) + (\frac{1}{3} + \frac{1}{3} + \frac{1}{3}) + \frac{1}{3} = 2 + \frac{1}{3}$
In other words, we get an integer part ($2$) and a left over ($\frac{1}{3}$). The left over part is always in the form of $k\frac{1}{b}$, with $0 \le k \textless b$. Thus, the smallest non-whole number we can get from $\frac{a}{b}$ is $qb + \frac{1}{b}$ with $qb$ being the integer part with $q \in \mathbb{N}_0$.

So assuming $\frac{a}{b}$ is not a whole number, the smallest left over we can have is $\frac{1}{b}$. So in-order to bump $\frac{a}{b}$ to the next whole number, it suffices to add $s = 1 - \frac{1}{b}$. This is $\textless 1$, which will not bump $\frac{a}{b}$ to the next whole number in case $\frac{a}{b}$ is a whole number, but still enough to bump $\frac{a}{b}$ to the next whole number in case $\frac{a}{b}$ is not a whole number.

Summing it up
So we know adding $s = 1 - \frac{1}{b}$ to $\frac{a}{b}$ will fulfill the equality: $\lfloor (\frac{a}{b} + s) \rfloor = \lceil \frac{a}{b} \rceil$. Thus we get:

$\lceil \frac{a}{b} \rceil = \lfloor (\frac{a}{b} + s) \rfloor = \lfloor (\frac{a}{b} + 1 - \frac{1}{b}) \rfloor = \lfloor \frac{a + b - 1}{b} \rfloor$
int a,b;
int myceil = (a + b - 1)/b;