Introduction

SPOJ problem ONEZERO asks for the smallest positive multiple of a given n whose decimal representation uses only the digits 0 and 1, and starts with 1. The key observation is that you should search over remainders modulo n, not over the full numbers themselves, because the actual candidate strings grow too large very quickly.

The Core Idea: BFS On Remainders

The official problem statement allows n up to 20000, so brute-forcing decimal strings is not practical. Instead, treat each remainder r as a node in a graph.

From remainder r, appending a digit creates two transitions:

• append 0: new remainder (r * 10) % n
• append 1: new remainder (r * 10 + 1) % n

Start from the number 1, whose remainder is 1 % n. Then run breadth-first search until you reach remainder 0.

BFS is correct here because it explores candidates in increasing number of digits, and with a fixed append order it also preserves lexicographic minimality among same-length candidates.

Why Remainders Are Enough

Suppose two different digit strings produce the same remainder modulo n. Any future digits appended to those strings will behave identically with respect to divisibility by n.

That means once you have visited a remainder, you never need to explore it again. Since there are only n possible remainders, the search space is finite and manageable.

C++ Implementation

This is a standard SPOJ-friendly approach.

1#include <bits/stdc++.h>
2using namespace std;
3
4string solve(int n) {
5    vector<int> parent(n, -1);
6    vector<char> digit(n);
7    vector<bool> visited(n, false);
8    queue<int> q;
9
10    int start = 1 % n;
11    q.push(start);
12    visited[start] = true;
13    digit[start] = '1';
14
15    while (!q.empty()) {
16        int rem = q.front();
17        q.pop();
18
19        if (rem == 0) {
20            string result;
21            while (rem != -1) {
22                result.push_back(digit[rem]);
23                rem = parent[rem];
24            }
25            reverse(result.begin(), result.end());
26            return result;
27        }
28
29        for (char d : {'0', '1'}) {
30            int next = (rem * 10 + (d - '0')) % n;
31            if (!visited[next]) {
32                visited[next] = true;
33                parent[next] = rem;
34                digit[next] = d;
35                q.push(next);
36            }
37        }
38    }
39
40    return "";
41}
42
43int main() {
44    ios::sync_with_stdio(false);
45    cin.tie(nullptr);
46
47    int t;
48    cin >> t;
49    while (t--) {
50        int n;
51        cin >> n;
52        cout << solve(n) << '\n';
53    }
54}

The arrays parent and digit let you reconstruct the answer once remainder 0 is found.

Reconstruction Strategy

When BFS discovers a new remainder, store:

• which previous remainder led to it
• which digit, 0 or 1, was appended

Once you hit remainder 0, walk backward through parent pointers to recover the digits, then reverse the result.

This avoids storing large candidate strings at every BFS state.

Complexity

The algorithm visits each remainder at most once, so:

• time complexity: O(n) per test case
• space complexity: O(n)

That is the right scale for the SPOJ limits.

Why DFS Or Brute Force Fails

Depth-first search does not guarantee the smallest valid answer first. Brute force over the full numbers also explodes in size because the candidate strings become very long.

The remainder graph is the reason the problem becomes easy enough to solve.

Common Pitfalls

A common mistake is building the actual decimal number in an integer type while searching. The answer can be far larger than 64-bit integers can hold.

Another mistake is forgetting that the search state is the remainder, not the whole string. Once you reduce the problem to remainders, the graph has only n nodes.

It is also easy to get reconstruction wrong by not storing the parent remainder and appended digit separately.

Summary

• Solve ONEZERO with BFS on remainders modulo n.
• Each state has two transitions: append 0 or append 1.
• Visiting remainders once keeps the search finite and efficient.
• Reconstruct the answer from parent pointers when remainder 0 is reached.
• Do not build giant integers during the search.