Packing Bits

Problem Statement Given a sequence of bits (0s and 1s) represented in a specific input format, pack them into bytes (groups of 8 bits) and output the result. format: First line: n, the total number of bits. Following...

Updated May 21, 2026

Track IOI

Year 1995

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Given a sequence of bits (0s and 1s) represented in a specific input format, pack them into bytes (groups of 8 bits) and output the result.

Input format:

First line: $n$, the total number of bits.
Following lines: bits given as integers (each either 0 or 1), up to 8 values per line.
Output format: Pack every 8 consecutive bits into one byte (most significant bit first) and output each byte as a decimal integer (0--255), with 8 values per output line. If the last group has fewer than 8 bits, pad with zeros on the right.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution Approach

This is a straightforward simulation problem.

Read all $n$ bits into an array.
Pad the array with zeros so that its length is a multiple of 8.
Process the bits in groups of 8. For each group, compute the byte value: \[ \text{byte} = \sum_{i=0}^{7} b_i \cdot 2^{7-i}. \]
Output the resulting bytes, 8 per line.

C++ Solution

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    vector<int> bits(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &bits[i]);

    // Pad to a multiple of 8
    while (bits.size() % 8 != 0)
        bits.push_back(0);

    int numBytes = bits.size() / 8;
    for (int i = 0; i < numBytes; i++) {
        int val = 0;
        for (int j = 0; j < 8; j++)
            val = val * 2 + bits[i * 8 + j];

        if (i > 0 && i % 8 == 0)
            printf("\n");
        else if (i > 0)
            printf(" ");
        printf("%d", val);
    }
    printf("\n");

    return 0;
}

Complexity Analysis

Time complexity: $O(n)$. Each bit is read once and each group of 8 bits is processed in constant time.
Space complexity: $O(n)$ to store all bits. This could be reduced to $O(1)$ by processing on the fly, accumulating 8 bits at a time before outputting.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1995 - Packing Bits
// Pack groups of 8 bits into bytes, output 8 bytes per line
// Time: O(n), Space: O(n)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);

    vector<int> bits(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &bits[i]);

    // Pad to multiple of 8
    while ((int)bits.size() % 8 != 0)
        bits.push_back(0);

    int numBytes = (int)bits.size() / 8;
    for (int i = 0; i < numBytes; i++) {
        int val = 0;
        for (int j = 0; j < 8; j++)
            val = val * 2 + bits[i * 8 + j];

        if (i > 0 && i % 8 == 0)
            printf("\n");
        else if (i > 0)
            printf(" ");
        printf("%d", val);
    }
    printf("\n");

    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1995/packing_bits/solution.texC++ implementationcompetitive_programming/ioi/1995/packing_bits/solution.cpp