Integer division and remainders

Integer division a / b in C++ gives the quotient without its fractional part, and a % b gives the remainder: 11 / 4 is 2 and 11 % 4 is 3. They answer how many whole groups fit and how much is left over.

Explanation

A shop packs 11 sweets into boxes of 4.

Fig. 1. 11 sweets fill 2 boxes of 4, and 3 are left. Packing all of them needs a third box.

Two boxes of 4 plus 3 give back 11: 11 = 2 · 4 + 3. The quotient 11 / 4 counts the full boxes, and the remainder 11 % 4 counts the sweets left over, so it is always less than 4. The fraction is dropped, because dividing two int variables gives an int: 7 / 2 is 3, while 7 / 2.0 is 3.5, since 2.0 is a double, a number with a fraction.

When a % b is 0, b divides a, and b is called a divisor of a: 12 % 4 is 0, so 4 is a divisor of 12, and n % 2 is 0 for every even n.

Lay boxes of length 4 along a number line: box 0 from 0 to 4, box 1 from 4 to 8, box −1 from −4 to 0. Point 11 lies in box 2, 3 past its start at 8, and 11 / 4 and 11 % 4 give exactly 2 and 3; now take point −11.

Fig. 2. C++ rounds toward zero (red). The box that contains -11 starts at -12 (blue).

Dropping the fraction rounds toward zero, so −2.75 goes up to −2 (red). But −11 lies in box −3, 1 past its start at −12: −3 · 4 + 1 = −11 (blue), and that is rounding down.

So when C++ gives a negative remainder, its quotient is 1 more than the rounded-down one, and its remainder is b less than the remainder from 0 to b - 1: subtract 1 from the quotient and add b to the remainder. For −11, −2 − 1 = −3 and −3 + 4 = 1, the box and the remainder of the blue arrow. In code these are a / b - (a % b < 0) and (a % b + b) % b, where a condition such as a % b < 0 counts as 1 when true and 0 when false. Both work for b > 0, which is what problems almost always have.

In C++

The template uses long long, the 64-bit integer, and assumes b > 0.

#include <iostream>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;                         // b > 0
    long long q = a / b;                   // quotient, rounded toward zero
    long long r = a % b;                   // remainder, sign of a: a == q * b + r
    bool divides = (a % b == 0);           // b divides a
    long long down = a / b - (a % b < 0);  // quotient rounded down
    long long m = (a % b + b) % b;         // remainder from 0 to b - 1
    cout << q << " " << r << " " << divides << " " << down << " " << m << "\n";
}

The outer % b in m matters when the remainder is already 0: -8 % 4 + 4 is 4.

Digits of a number

The remainder n % 10 is the last digit of n, and the quotient n / 10 is the number without it. Repeating both in a loop takes the digits from the last to the first:

while (n > 0) {
    int d = n % 10;
    cout << d << " ";
    n /= 10;
}

Fig. 3. n = 4096: the digits come out as 6, 9, 0, 4.

For a negative n the loop doesn't run at all, and with n != 0 it would print −3 −2 −1 for −123, because -123 % 10 is −3. Take abs(n), the value without its sign, first.

Time and cycles

/ and % are read left to right, so t / 60 % 60 is (t / 60) % 60, the whole minutes without the full hours:

int h = t / 3600, mi = t / 60 % 60, s = t % 60;   // 3725 -> 1 2 5, that is 1:02:05

On a 24-hour clock, 0 comes after 23, so k hours after hour h is (h + k) % 24. Going back needs the remainder from 0 to 23, because (1 - 3) % 24 is −2, not 22:

int later = (h + k) % 24;
int earlier = ((h - k) % 24 + 24) % 24;   // h = 1, k = 3 -> 22

Days of the week numbered 0 to 6 work the same way with 7. So do times past midnight: from t1 to t2 there are ((t2 - t1) % 86400 + 86400) % 86400 seconds, 6300 (1:45:00) from 23:30:00 to 01:15:00.

Rounding up

Packing all 11 sweets takes 3 boxes, one more than 11 / 4. Adding 1 fails for 12 sweets: they need 3 boxes, not 4. Instead, add 3, one less than the box size, before dividing. With 11 sweets the extra 3 reach into the dashed box of Fig. 1, so (11 + 3) / 4 is 3; with 12 the last box is already full, and (12 + 3) / 4 is still 3.

long long up = (a + b - 1) / b;           // a >= 0
long long up2 = a / b + (a % b > 0);      // any sign of a

For −5 and 4 the first form gives 0, but −1.25 rounded up is −1. The second form adds 1 only for a positive remainder, which works for any sign because C++ already rounds a negative quotient up. Near 2 \cdot 10^9, a + b - 1 doesn't fit in an int: use long long or the second form.

Numbering from 1

Flats are numbered from 1, with 4 flats on each floor, and floors are numbered from 1 too. Subtract 1 first, so that the numbers start from 0 like the sweets: flat 14 becomes 13, 13 / 4 is 3 full floors below it, and flat 14 is on floor 3 + 1 = 4.

Common mistakes

• Dividing too early. 30 / 100 * 50 is 0, because 30 / 100 is already 0. Multiply first (30 * 50 / 100 is 15) or divide by a double.

• Counting digits with while (n > 0) { cnt++; n /= 10; }. For n = 0 it counts 0 digits, but 0 has one. Use do { cnt++; n /= 10; } while (n > 0);.

Similar techniques

• Modular arithmetic keeps remainders through sums and products, for answers asked modulo 10^9 + 7.

• Bitmasks use x >> 1 and x & 1 to divide by 2 and test for odd numbers. For a negative x, x >> 1 rounds down: -7 >> 1 is −4, while -7 / 2 is −3.

• Floating-point numbers are for answers that are fractions, such as an average, not for rounding integer quotients.

• The Euclidean algorithm finds the greatest common divisor by repeated %.

Practice