Smallest All-Ones Multiple - Solution & Explanation

Problem Overview: Given an integer n, find the smallest positive integer composed only of the digit 1 (like 1, 11, 111, ...) that is divisible by n. The result can grow extremely large, so constructing the full integer directly quickly becomes impractical.

Approach 1: Brute Force Number Construction (Large Integer Simulation) (Time: O(k^2), Space: O(k))

The most straightforward idea is to repeatedly build numbers consisting only of 1. Start with 1, then 11, then 111, and check divisibility by n each time. This works in theory but fails in practice because the number grows exponentially in digits. Standard integer types overflow quickly, forcing the use of big integers or strings. Each divisibility check becomes expensive as the number length grows, resulting in roughly O(k^2) work where k is the length of the resulting number. This approach mainly helps build intuition but is not suitable for large inputs.

Approach 2: Simulation with Modulo Operation + Remainder Set (Time: O(n), Space: O(n))

The key observation: you never need the full number. Only the remainder modulo n matters. Suppose the current number of repeated ones has remainder r. Appending another 1 forms a new number whose remainder is (r * 10 + 1) % n. By repeatedly applying this transition, you simulate growing numbers while only storing remainders.

Track visited remainders using a hash table. If remainder 0 appears, the constructed sequence of ones is divisible by n. If a remainder repeats, the process entered a cycle and no such number exists. This happens when n has factors 2 or 5, since numbers composed only of 1 cannot end with even digits or 5. The algorithm effectively explores at most n unique remainders, giving O(n) time complexity.

This technique is common in problems involving repeated digit construction and modular arithmetic. The core idea comes from math properties of remainders and cycle detection.

Recommended for interviews: The modulo simulation with a remainder set is the expected solution. Interviewers want to see that you avoid constructing huge integers and instead reason about remainders. Mentioning the brute force idea first shows problem understanding, while switching to the remainder-based approach demonstrates algorithmic maturity and familiarity with hash table based cycle detection.