This post was originally written on Codeforces; relevant discussion can be found here.

There were a few instances on CF according to which it seems that quite a few people aren’t very comfortable with floor and ceiling functions (and inequalities in general) — for instance, here and here. This inspired me to write a hopefully short post on how to systematically work with these topics.

Note that I will not define what a real number is, or do anything that seems too non-elementary. Also, for the foundational stuff, I will rely on some correct intuition rather than rigour to build basic ideas, and the systematic logically correct way of reasoning will be used later. The idea behind this post is to just help you understand how to reason about the topics we’ll cover.

Recap: basic inequalities

Before we jump ahead to floors and ceilings, we need to talk about inequalities. I will assume that you know something about the number line. Let’s recap some informal definitions:

  • We say that \(a < b\) if and only if the number \(a\) comes before the number \(b\) on the number line. Here number refers to real numbers.
  • We say that \(a = b\) if and only if \(a\) and \(b\) coincide on the number line.
  • We say that \(a > b\) if and only if \(b < a\), i.e., \(a\) comes after \(b\) on the number line.
  • We say that \(a \le b\) if and only if one of \(a < b\) or \(a = b\) holds.
  • We say that \(a \ge b\) if and only if one of \(a > b\) or \(a = b\) holds.

For the sake of brevity, we will abbreviate “if and only if” to iff. We will often use \(P \iff Q\) in math notation to indicate that \(P\) is true iff \(Q\) is true. For a unidirectional implication of the form “if \(P\) is true, then \(Q\) is also true”, we will write \(P \implies Q\), and read it as \(P\) implies \(Q\).

Here’s a fact that people often use intuitively, called the Law of Trichotomy:

  • Exactly one of the following relations is true: \(a < b\), \(a = b\), \(a > b\).

This is useful a lot of times when you try to break things into cases, and try to look for contradictions.

A corollary of this is the following definition of the relations in terms of \(<\) and negation (you can use any relation other than \(=\) to get all other operations):

  • \(a = b\) iff \(a \not < b\) and \(b \not < a\).
  • \(a > b\) iff \(b < a\).
  • \(a \le b\) iff \(b \not < a\).
  • \(a \ge b\) iff \(a \not < b\).

Now note that if we have some results about \(<\), using the above relations, we can come up with relations corresponding to these operations too.

We can also write these relations in terms of \(\le\) — I leave this as an exercise for you to confirm that you’ve understood the logic behind these.

I recommend understanding why these make sense, so that you can reason about directions and inequalities more easily.

Chaining these relations

Let’s say \(a R b\) and \(b R c\) are true, where \(R\) is any one of \(<, >, =, \le, \ge\). Then it is easy to show that \(a R c\) is also true. This allows us to chain inequalities, and write things like \(a < b < c\) and remembering that as we read the expression from left to right, the terms only increase.

This property is called transitivity, and is well-studied in other contexts too. But for our purposes, it just makes our life simpler.

At this point, it is very important to note two more things:

  • If \(a < b\) and \(b > c\), we can’t say anything about the order of \(a\) and \(c\). This is a rookie mistake that happens a lot.
  • \(<\) is a stronger statement than \(\le\). In particular, if we have something like \(a < b\) and \(b \le c\), then it is impossible that \(a = c\). So we can in fact say that \(a < c\), rather than the weaker statement \(a \le c\). Mathematically, you can show this by reasoning as follows: \(b \le c\) means that either \(b < c\) or \(b = c\). In the first case, the chaining is trivially true. In the second case, since \(b = c\), the positions of \(b\) and \(c\) on the number line coincide, so the result is again true. (For the pedantic reader: the second part of this argument is referring to the fact that \(<\) is a well-defined relation — in terms of respecting equality).

How arithmetic operations affect inequalities

This is what many people don’t internalize very well, or are simply not exposed to. At the risk of being too verbose, I will explain some interactions of arithmetic operations and inequalities (we will focus on \(<\), but such relations can be developed for other relations as well — like \(>, \le\) and their combinations — and that is left as an exercise):

  • Addition/subtraction: let’s say you have an inequality \(a < b\). If you shift both things by the same amount on the number line, their relative positions won’t get flipped. In other words, if we add a constant \(c\) to both \(a\) and \(b\), the relative ordering of \(a+c\) and \(b+c\) is the same as that of \(a\) and \(b\). That is, \(a < b\) implies \(a + c < b + c\). The same holds for subtraction. So this implies some sort of a cancellation law:

\[a < b \iff a + c < b + c\]

  • Multiplication by \(0\): Both sides of any inequality become \(0\), so upon multiplication by \(0\), inequalities become equalities.

  • Multiplication by a positive number: let’s say you have an inequality \(a < b\). This means \(0 < b - a\), or in other words, \(b - a\) is a positive number. If we multiply it by a positive number \(c\), it will remain positive. That is \(0 < c(b - a)\). Adding \(ac\) to both sides gives \(ac < bc\). So:

\[c > 0, a < b \implies ac < bc\]

  • Multiplication by a negative number: let’s say you have an inequality \(a < b\) and a negative number \(c < 0\). Clearly, we have \(a(-c) < b(-c)\) from the previous result. Adding \(ac + bc\) to both sides gives \(bc < ac\), or \(ac > bc\). That is, the sign of the inequality gets flipped. So:

\[c < 0, a < b \implies ac > bc\]

  • Adding two inequalities that go the same way: let’s say you have two inequalities \(a < b\) and \(c < d\). Is it true that \(a + c < b + d\)? Let’s try to reason about it using the previous result. Let’s subtract \(c\) from both sides of the inequality (we can do this by the previous result). Then \(a + c < b + d \iff a < b + d - c\). Note that since \(c < d\), doing the same thing gives us \(0 < d - c\). This essentially means that \(d - c\) is a positive number. If we shift \(b\) by a positive number to the right, we are moving \(b\) farther from \(a\), and hence the shifted \(b\) should still be \(> a\). This means that \(a < b + d - c\). Using the previous equivalence, \(a + c < b + d\) is indeed true. All in all, we have shown that

\[a < b, c < d \implies a + c < b + d\]

  • Subtracting two inequalities that go the opposite way: let’s say you have two inequalities \(a < b\) and \(c > d\). Is it true that \(a - c < b - d\)? Note that multiplying \(c > d\) by \(-1\) gives \(-c < -d\). So we have \(a - c < b - d\) by our previous result. We have shown that

\[a < b, c > d \implies a - c < b - d\]

NOTE: Subtracting inequalities of the same type and adding inequalities of the opposite type does not work, and I leave it as an exercise for you to see which steps in the above proofs fail.

Multiplying and dividing inequalities is significantly more complicated, but they can be treated with the same ideas. More specifically, for multiplying two inequalities, you have to make cases on the signs of the 4 terms. For division, the idea is the same, but additionally you have to take care that some denominator is not 0.

Floors and ceilings

Let’s start out by the definition of the floor function and the ceiling functions:

  • The floor function is a function \(\lfloor \cdot \rfloor : \mathbb{R} \to \mathbb{Z}\) such that for all real numbers \(x\), \(\lfloor x \rfloor\) is the integer \(n\) such that \(n \le x < n + 1\).

  • The ceiling function is a function \(\lceil \cdot \rceil : \mathbb{R} \to \mathbb{Z}\) such that for all real numbers \(x\), \(\lceil x \rceil\) is the integer \(n\) such that \(n - 1 < x \le n\).

Clearly, if such \(n\) exist, they are unique.

Why do these definitions make sense? Note that intervals of the form \([n, n + 1)\) for integer \(n\) cover the number line disjointly (this is not a rigorous proof, but I don’t want to deal with real numbers), so \(x\) will always be in one of these intervals. The same property holds for intervals of the form \((n - 1, n]\).

As a special case, when \(x\) is an integer, both the ceiling and the floor functions return \(n\).

NOTE: Remember that \(\lfloor 1.5 \rfloor = 1\), but \(\lfloor -1.5 \rfloor = -2\), and not \(-1\).

In fact, we can notice the following:

  • \(\lfloor x \rfloor\) is the largest integer \(n\) such that \(n \le x\).
  • \(\lceil x \rceil\) is the smallest integer \(n\) such that \(x \le n\).

The proof follows from the definition (we will show this only for floor, the ceiling case is analogous): let’s say that this is not true, and there is some \(a > n\) such that \(a \le x\). \(a > n\) means \(a \ge n + 1\). But we know that \(x < n + 1 \le a\), so \(x < a\). This is a contradiction.

Note: As a consequence of the above fact, we have \(\lfloor x \rfloor \le \lceil x \rceil\), and the difference between them is \(1\) iff \(x\) is not an integer; when \(x\) is an integer, they are equal to \(x\).

We can rephrase these statements in the following ways that can be useful while solving problems.

  • For an integer \(n\) and a real number \(x\), the following holds: \(n \le x \iff n \le \lfloor x \rfloor\).
  • For an integer \(n\) and a real number \(x\), the following holds: \(n \ge x \iff n \ge \lceil x \rceil\).

This is especially important because these kinds of iff statements help us reduce the large number of cases that can arise while framing and solving inequalities. For an example, consider this comment.

Let’s try to rephrase the original definition into another way too. \(n \le x < n + 1\) is equivalent to the two inequalities \(n \le x\) and \(x < n + 1\). The latter is equivalent to \(x - 1 < n\). So combining these again shows that \(x - 1 < n \le x\). These steps are reversible, so this means this can also function as an alternate definition of the floor function. Doing this similar for the ceiling function, we have the following properties (that are also alternate definitions):

  • \(x - 1 < \lfloor x \rfloor \le x\)
  • \(x \le \lceil x \rceil < x + 1\)

It is sometimes useful to think in terms of the fractional part of a number (i.e., distance from floor), since it is guaranteed to be a positive real number less than 1. Similarly, distance to ceiling is helpful too.

Some more properties of floors and ceilings

Let’s see what happens to the floor of a real number when we add (or equivalently, subtract) an integer.

Let \(n’ = \lfloor x + a \rfloor\) where \(a\) is an integer. This is equivalent to saying that \(n’ \le x + a < n’ + 1\), which is equivalent to \(n’ - a \le x < n’ - a + 1\). Since \(n’\) is an integer, \(n’ - a\) is also an integer. Hence this is equivalent to saying that \(n’ - a = \lfloor x \rfloor\). In other words, we have shown that

\[a \in \mathbb{Z} \implies \lfloor x + a \rfloor = \lfloor x \rfloor + a\]

Similarly, we can show that

\[a \in \mathbb{Z} \implies \lceil x + a \rceil = \lceil x \rceil + a\]

However, this kind of an identity doesn’t hold for multiplication by an integer in general. For example, \(\lfloor 1.5 \rfloor = 1\), and \(\lfloor 2 \cdot 1.5 \rfloor = 3 \ne 2 \cdot \lfloor 1.5 \rfloor\).

Note that by the same example, we can show that \(\lfloor x + y \rfloor\) is NOT equal to \(\lfloor x \rfloor + \lfloor y \rfloor\) in general (and something similar for ceiling). However, it can be shown that the following are true:

\[\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x + y \rfloor \le \lfloor x \rfloor + \lfloor y \rfloor + 1\]

\[\lceil x \rceil + \lceil y \rceil - 1 \le \lceil x + y \rceil \le \lceil x \rceil + \lceil y \rceil\]

Let’s now look at what happens when we multiply the argument of the functions by \(-1\).

From \(n \le x < n + 1 \iff -n - 1 < -x \le -n\), we can note that \(-\lfloor x \rfloor = \lceil -x \rceil\). By replacing \(x\) by \(-x\) in this relation, we have \(\lfloor -x \rfloor = - \lceil x \rceil\).

Since the floor and ceiling functions both return integers, applying any amount of floor or ceiling functions to the result will not change their value after one of them is already applied once.

One non-trivial property that sometimes helps is the following:

For an arbitrary positive integer \(n\) and real number \(x\):

  • \(\lfloor \frac{\lfloor x \rfloor}{n} \rfloor = \lfloor \frac{x}{n} \rfloor\)
  • \(\lceil \frac{\lceil x \rceil}{n} \rceil = \lceil \frac{x}{n} \rceil\)

Proving this is simple and is left as an exercise for the reader. Alternatively, it can be shown via the proof of the property below.

Another more general property is the following (reference: Concrete Mathematics, p71):

Let \(f(x)\) be any continuous, monotonically increasing function with the property that \(f(x)\) being an integer implies \(x\) being an integer. Then we have \(\lfloor f(x) \rfloor = \lfloor f(\lfloor x \rfloor) \rfloor\), and a similar thing holds for the ceiling function.

The proof is as follows. There is nothing to prove for \(x\) being an integer. Consider \(x\) being a non-integer. Since \(\lfloor \cdot \rfloor\) and \(f\) are both non-decreasing functions, we have \(\lfloor f(\lfloor x \rfloor) \rfloor \le \lfloor f(x) \rfloor\). Suppose that the inequality is strict — in that case, since \(f\) is monotonic and continuous, there is a \(\lfloor x \rfloor < y \le x\) such that \(f(y) = \lfloor f(x) \rfloor\). Then \(y\) is an integer because of the property that \(f\) has. But there can not be another integer between floor of a number and itself, which is a contradiction.

For more properties and applications, I would refer you to the Wikipedia article on these functions.

Some natural applications of floors and ceilings

  • Quotient and remainder: The quotient on dividing a positive integer \(a\) by another positive integer \(b\) is by definition \(\lfloor a / b \rfloor\). The remainder is \(a - b \lfloor a / b \rfloor\).
  • To count the number of multiples of \(a\) that are \(\le n\), we note that if there are \(k\) multiples, then the largest multiple of \(a\) is \(ka\), and it should be \(\le n\). Hence \(k \le n/a\). This is also a sufficient condition for there being at least \(k\) multiples of \(a\) at most \(n\). So \(k = \lfloor n / a \rfloor\) by maximality of \(k\).

Examples of reasoning with the developed tools

Now that we have some results in our toolbox, we’ll show how to actually solve problems cleanly without getting stuck thinking about multiple cases at once. We’ve already shown some ways of using these while deriving other results, so we’ll keep this short and I’ll just link to some problems instead.

Some identities and bounds

I’ll list out some non-trivial identities and bounds, and proving them is left as an exercise.

  • Floors and ceilings for fractions: For a positive integer \(b\) and an arbitrary integer \(a\), we have \(\lceil a/b \rceil = \lfloor (a + b - 1)/b \rfloor\).
  • Gauss’ property: For positive integers \(m, n\), we have \(\sum_{i = 0}^{n - 1} \lfloor im/n \rfloor = ((m - 1)(n - 1) + \gcd(m, n) - 1) / 2\). To prove this, try looking at the number of points below the line \(y = mx/n\) inside the rectangle with corners \((0, 0)\) and \((m, n)\).
  • Hermite’s identities: For a positive integer \(n\) and a real number \(x\), the following are true: \(\lfloor nx \rfloor = \sum_{i = 0}^{n - 1} \lfloor x + i/n \rfloor\) and \(\lceil nx \rceil = \sum_{i = 0}^{n - 1} \lceil x - i/n \rceil\). This can be proved by making cases on whether the fractional part (respectively, distance to ceiling) is between \(i/n\) and \((i + 1)/n\).
  • Harmonic bounds: \(\sum_{i = 1}^n \lfloor x / i \rfloor \le x \sum_{i = 1}^n 1/i = O(x \log n)\). As a consequence, a sieve that considers all divisors from \(1\) to \(n\) for a total of \(x\) consecutive integers takes \(O(x \log n)\) time. This is why both the normal sieve of Eratosthenes and the segmented variant are fast enough. This also shows that the sum of divisors of a positive integer \(n\) is at most \(O(n \log n)\).

Programming language specific details

For the sake of sanity, it is recommended to ensure that whenever you are trying to perform integer division in any programming language, try to convert it into a form where the denominator is positive. However, for most languages, it is always true that (a / b) * b + (a % b) evaluates to a.

There are typically two behaviors when performing integer division with a positive divisor:

  • Computing the floor in all cases: this is the case for Python, for example. Hence a // b will give \(\lfloor a / b \rfloor\), and a % b will give the non-negative remainder when \(a\) is divided by \(b\).
  • Rounding the result towards \(0\): this is the case in C++, for example. One reason behind this is to prevent overflow when multiplying the result by the denominator. So, for positive \(a\), the behaviour is the same as in Python, but for negative \(a\), it returns \(\lceil a / b \rceil\), and a % b gives the negative distance to the corresponding multiple of \(b\).

Note that to compute the ceiling of some \(a / b\) for positive integer \(b\) and integer \(a\), we can use the result mentioned earlier: \(\lceil a / b \rceil = \lfloor (a + b - 1) / b \rfloor\). Implementing code for correctly computing floors and ceilings in both C++ and Python is an instructive exercise.

Keep in mind that std::floor and std::ceil are operations on floating point numbers, and their results are also floating point numbers. Hence they might not be exact when converted to integers, and hence it is not recommended to use them for most practical purposes.