Why Base64, and What It Costs

By the end of this lesson your program answers one question about base64 without encoding anything: given a number of bytes, how many base64 characters do they become, and how many of those are padding. Every later lesson's output is checked against it.

How it works

A byte is one unit of raw data, a number from 0 to 255: a 100-byte file is 100 such numbers in a row. Some channels carry only printable text — an email body, a URL, a certificate file you paste into a text box. Base64 re-spells arbitrary bytes in a small set of safe characters so they survive the trip.

The exchange rate never changes: base64 reads the input in groups of 3 bytes and writes exactly 4 characters per group. Four out for every three in is 4/3 of the original size — the roughly 33% overhead.

Take the five bytes of Hello and lay them out in groups of three:

bytes:   H  e  l  |  l  o
         group 1  |  group 2, short: only 2 bytes

chars:   c  c  c  c | c  c  c  =
         4 chars    | 4 chars, last slot has no byte to carry

total:   8 characters, 1 of them '='

A short last group still costs a whole four-character group, so an encoded length is always a multiple of 4. The slots in it with no input byte to carry are written as =. Those = characters are the padding — the second number this lesson prints, and the one the starter calls pads. What the other characters look like is lesson 4's job; here only the count matters.

Count a few by hand. n is the byte count; the leftover is what remains after taking as many whole 3-byte groups out of it as possible. Languages spell that leftover n % 3 (read: n mod 3) — the remainder, always 0, 1 or 2.

   n | groups | n % 3 | chars | '='
   0 |    0   |   0   |    0  |  0
   1 |    1   |   1   |    4  |  2
   2 |    1   |   2   |    4  |  1
   3 |    1   |   0   |    4  |  0
   5 |    2   |   2   |    8  |  1
 100 |   34   |   1   |  136  |  2

The groups column counts a partial last group as a whole one; each group costs 4 characters. The padding count depends only on n % 3: 0 gives 0 pads, 1 gives 2 pads, 2 gives 1 pad.

To round up without floating point, add 2 before dividing: groups = (n + 2) / 3 with integer division (remainder discarded), then chars = 4 * groups. The + 2 pushes a partial group up to the next whole one and leaves multiples of 3 alone. Languages spell integer division differently — the starter comment for your language names the operator. For n = 100: (100 + 2) / 3 = 34 groups, so 4 * 34 = 136 characters, and 100 % 3 is 1, so 2 pads — the 136 2 row. For n = 0: (0 + 2) / 3 = 0 groups, so 0 0 — the formula already covers the empty input, and there is no special case to write. Dividing the other way round, 4 * n / 3, gives 5 for n = 4, where the answer is 8.

The algorithm

for each line of input:
    n = the integer on that line
    groups = <round n up to a whole number of 3-byte groups>
    chars  = <four characters per group>
    pads   = <0, 2 or 1, decided by n % 3>
    print chars, one space, pads

What the grader runs

Input arrives on stdin (the stream your program reads; printing goes to stdout) as zero or more lines, each one decimal integer n with 0 <= n <= 1000000. No blank lines. For each input line print one line: the total base64 character count including padding, a single space, then the number of = characters.

input:
0
1
2
3
5
100

output:
0 0
4 2
4 1
4 0
8 1
136 2

input:
2
3
4

output:
4 1
4 0
8 2

Empty stdin produces empty stdout. Print exactly this, one result per line, a single space between the numbers, newline-terminated, nothing else.

Notes

• n = 0 is the only input answering 0 0; a formula that always adds one group answers 4 2 and fails.
• Hidden tests sit on both sides of every boundary: 2, 3, 4, 6, 7, and 999999 and 1000000.
• The most common mistake is 4 * n / 3 with truncating division: right for multiples of 3, wrong otherwise.
• Primary source: RFC 4648, https://www.rfc-editor.org/rfc/rfc4648

Your exercise

Implement the size function in the starter: given a byte count n, return how many base64 characters those bytes occupy, padding included, and how many are =. The starter already reads the integers, calls the function and prints; only the arithmetic is missing. The likeliest mistake is 4 * n / 3; the next is n = 0 printing 4 2.