Is Smallest All-Ones Multiple easy or hard?

Smallest All-Ones Multiple is typically considered a medium-level problem. The challenge is recognizing that constructing the full number is unnecessary and that the problem can be solved using remainder simulation and cycle detection.

Smallest All-Ones Multiple Python/Java solution

Most implementations follow the same pattern across languages. Maintain a remainder variable, repeatedly compute (remainder * 10 + 1) % n, and store remainders in a set. Python, Java, C++, Go, and TypeScript versions all run in O(n) time with O(n) additional memory.

How to solve Smallest All-Ones Multiple in O(n)?

Simulate the number using modular arithmetic. Start with remainder = 1 % n, then repeatedly compute remainder = (remainder * 10 + 1) % n while tracking visited remainders in a hash set. When the remainder becomes 0, the constructed sequence of ones forms a multiple of n. If a remainder repeats, the process cycles and no valid number exists.

What is the best approach for Smallest All-Ones Multiple?

The optimal approach simulates the number using modulo arithmetic instead of building the full integer. Track the remainder of the current number and update it using (remainder * 10 + 1) % n. A hash set stores previously seen remainders to detect cycles. This runs in O(n) time and O(n) space.

Is Smallest All-Ones Multiple asked at Google/Amazon/Meta?

Problems involving repeated digits with modular arithmetic and remainder cycles appear in interviews at large tech companies. Variants are commonly asked at companies like Google, Amazon, and Meta to test understanding of number theory and state-cycle detection using hash sets.

What data structure is used in Smallest All-Ones Multiple?

A hash set (or hash table) stores previously seen remainders during the simulation. This prevents infinite loops and allows detection of cycles when the same remainder appears again. The rest of the algorithm relies on simple modulo math operations.

What is the time complexity of Smallest All-Ones Multiple?

The optimal algorithm runs in O(n) time because there are only n possible remainders when dividing by n. Each step generates a new remainder using (r * 10 + 1) % n and checks it in a hash set. Space complexity is also O(n) due to storing visited remainders.

Description Hints 3 Solution Video 12:33

3790. Smallest All-Ones Multiple

Medium46.8% acceptance

You are given a positive integer k.

Find the smallest integer n divisible by k that consists of only the digit 1 in its decimal representation (e.g., 1, 11, 111, ...).

Return an integer denoting the number of digits in the decimal representation of n. If no such n exists, return -1.

Example 1:

Input: k = 3

Output: 3

Explanation:

n = 111 because 111 is divisible by 3, but 1 and 11 are not. The length of n = 111 is 3.

Example 2:

Input: k = 7

Output: 6

Explanation:

n = 111111. The length of n = 111111 is 6.

Example 3:

Input: k = 2

Output: -1

Explanation:

There does not exist a valid n that is a multiple of 2.

Constraints:

2 <= k <= 10⁵

Topics

Hash Table Math

Hints open one at a time

Hint 1

Notice that n % k should be 0.

Hint 2

Build the number digit-by-digit using only modulo k. Start with remainder rem = 1 % k. Repeatedly update rem = (rem * 10 + 1) % k while counting how many 1s have been appended.

Hint 3

Continue until rem == 0 or a remainder repeats (which indicates a cycle and that no such n exists).

12:33

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minAllOneMultiple(self, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution