1015. Smallest Integer Divisible by K

MediumHash TableMath
Leetcode Link

Problem Description

This problem requires finding the smallest positive integer n which consists entirely of the digit 1 and is divisible by a given positive integer k. We are interested in the length of such an integer n, rather than the number itself. The challenge is that n could be very large, potentially exceeding the limits of standard data types used in programming (like a 64-bit signed integer).

Here are the key points to understand:

  • n must be made up of the digit 1 repeated one or more times. Some examples of such numbers are 1, 11, 111, 1111, and so on.
  • We should find the smallest such number n that is divisible by the given k.
  • The length we are after is the count of the digit 1 in this smallest number n.
  • If there is no such n that can be divisible by k, we should return -1.

The main challenge in solving this problem is to handle the potentially large size of n without running into overflow issues.

Intuition

To arrive at the solution for this problem, we need a way to check if a number consisting only of the digit 1 is divisible by k without having to actually construct the potentially very large number. The insight here is to use the properties of modular arithmetic.

Here's the intuition behind the solution:

  • We start by checking if 1 % k is 0, which means 1 is divisible by k. If it is, we return 1 since this is the smallest possible length.
  • If not, then we iteratively build the number n by appending the digit 1 to it and simultaneously calculating n % k for each new n. This operation is equivalent to (n * 10 + 1) % k.
  • This process continues until we either find that n % k == 0 (meaning n is divisible by k) or we have iterated k times without finding such an n.
  • We iterate up to k times because of a pigeonhole principle - if n is not found to be divisible by k after k iterations, it will never be, and we return -1.

Essentially, the solution relies on the fact that a number that only contains the digit 1 can be built iteratively, and at each step, we can check divisibility using modular arithmetic, avoiding the need to deal with very large numbers directly. If the remainder is ever zero, we've found our number n and we return its length, corresponding to the number of iterations.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Solution Approach

The solution provided is an implementation of a direct simulation, leveraging modular arithmetic. There is no need for any complex data structures or algorithms beyond basic arithmetic operations and a for-loop to control the iterations. Here is how the implementation works:

  1. Initialize n to 1 % k. This is because we start by analyzing the smallest number made up only of the digit 1, which is the number 1 itself.

  2. Loop from 1 to k using a for-loop, which represents the number of digits in n and not the number itself. The reason for this restriction is the pigeonhole principle mentioned earlier, which suggests that within k steps, a remainder should repeat, leading to a cycle without finding a divisible number if it has not already been found.

  3. Inside the loop, we first check if the current remainder n is 0. If this is the case, the number represented by the current length i (number of digits in n) is divisible by k, and we return i as the result.

  4. If n is not zero, we update n by trying to append a digit 1 to our number, which is mathematically represented by n = (n * 10 + 1) % k. The multiplication by 10 shifts the digits left, adding a new zero to the end, and then we add 1 to include the new digit 1 at the lowest place value. We use modulus k to keep n within a manageable size, which is also the remainder we are interested in.

  5. If we complete the for-loop without finding a number n that is divisible by k (i.e., without the remainder becoming zero), we return -1. This implies that no number consisting solely of 1s up to the length of k is divisible by k, and by the pigeonhole principle, no such number exists.

In summary, the solution uses a smart brute-force method to simulate the actual division operation on numbers consisting of the digit 1 only, while calculating the remainders using modular arithmetic, thus avoiding dealing with very large numbers that could lead to overflow issues.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's take a simple example where k = 3 to illustrate how the solution approach works in practice:

  1. We start by initializing n with the value of 1 % 3. Upon calculation, 1 % 3 equals 1 since 1 divided by 3 leaves a remainder of 1.

  2. We then begin our for-loop, which will iterate from 1 to k (in this case, 3). For each iteration i, we perform the following steps:

    a. On the first iteration (i = 1), we check if n is 0. It is not (n = 1), so we continue.

    b. Since n is not 0, we then update n as (n * 10 + 1) % k. For the first iteration: (1 * 10 + 1) % 3 equals 11 % 3, which gives us a remainder of 2. We then proceed to the next iteration with n now equal to 2.

  3. In the second iteration (i = 2), we find that n is not 0, so we perform the update step again: (n * 10 + 1) % k becomes (2 * 10 + 1) % 3, which simplifies to 21 % 3. This gives us a remainder of 0.

  4. As soon as we get a remainder of 0, we know that the number 21 (which consists of 2 digits of 1) is divisible by 3. Thus, we return the current iteration number i, which in this case is 2.

In conclusion, for this example, the smallest number consisting entirely of the digit 1 that is divisible by 3 has a length of 2 (the number is 11). Therefore, the function would return 2.

Solution Implementation

1class Solution:
2    def smallestRepunitDivByK(self, k: int) -> int:
3        # Initialize remainder of the first repunit which is 1
4        remainder = 1 % k
5      
6        # Iterate through each length from 1 to k
7        for length in range(1, k + 1):
8            # If the remainder is 0, we have found the smallest length
9            if remainder == 0:
10                return length
11            # Update the remainder by appending a '1' to the current number and taking mod
12            remainder = (remainder * 10 + 1) % k
13          
14        # If no such length was found, return -1 indicating no solution exists
15        return -1
16
1class Solution {
2    public int smallestRepunitDivByK(int k) {
3        // Initialize remainder with 1 modulo k, this corresponds to the repunit '1'
4        int remainder = 1 % k;
5      
6        // Loop through numbers from 1 to k to find the smallest repunit
7        for (int length = 1; length <= k; ++length) {
8            // If the remainder is 0, then we have found a repunit of length 'length' that is divisible by k
9            if (remainder == 0) {
10                return length;
11            }
12            // Update the remainder for the next iteration which corresponds to appending another '1' to the repunit
13            // This is equivalent to shifting the current number left by one digit (multiply by 10) and adding another '1'
14            remainder = (remainder * 10 + 1) % k;
15        }
16      
17        // If no such repunit is found that is divisible by k within the first k numbers, return -1
18        return -1;
19    }
20}
21
1class Solution {
2public:
3    /**
4     * Returns the length of the smallest positive integer that is 
5     * composed solely of ones and is divisible by 'k'.
6     *
7     * @param k The divisor to check against.
8     * @return The length of the smallest repunit divisible by 'k', 
9               or -1 if none exists within 'k' digits.
10     */
11    int smallestRepunitDivByK(int k) {
12        // Initialize remainder 'currentRemainder' with the remainder of 1 divided by 'k'.
13        int currentRemainder = 1 % k;
14      
15        // Iterate up to 'k' times to find the smallest repunit.
16        for (int i = 1; i <= k; ++i) {
17            // If the current remainder is 0, we have found a repunit divisible by 'k'.
18            if (currentRemainder == 0) {
19                return i; // Return the current length 'i'.
20            }
21          
22            // Calculate the next remainder when 'i+1' ones are considered.
23            // This is akin to appending another '1' to the end of the repunit.
24            // The % k ensures we work with remainders reducing the overall number size.
25            currentRemainder = (currentRemainder * 10 + 1) % k;
26        }
27      
28        // If we have not returned within the loop, no repunit of length <= 'k' is divisible by 'k'.
29        // Therefore, return -1 to indicate failure.
30        return -1;
31    }
32};
33
1/**
2 * Finds the smallest length of a positive integer number consisting only of ones ('1')
3 * that is divisible by the given integer `k`.
4 * If there is no such number, the function returns -1.
5 * 
6 * @param {number} k - An integer by which the repunit (a number consisting only of ones) has to be divisible.
7 * @return {number} - The length of the smallest repunit divisible by `k`, or -1 if no such repunit exists.
8 */
9function smallestRepunitDivByK(k: number): number {
10    // Initialize the remainder when dividing '1' by 'k'.
11    let remainder = 1 % k;
12    // Loop up to 'k' times to find the smallest repunit divisible by 'k'.
13    for (let length = 1; length <= k; ++length) {
14        // If the current remainder is 0, a repunit number that is divisible by 'k' has been found.
15        if (remainder === 0) {
16            return length;
17        }
18        // Calculate the next remainder when adding another '1' to the repunit and taking the modulus with 'k'.
19        remainder = (remainder * 10 + 1) % k;
20    }
21    // If no repunit divisible by 'k' has been found after 'k' iterations, return -1.
22    return -1;
23}
24
Not Sure What to Study? Take the 2-min Quiz：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(K). This is because there is a for-loop that iterates up to k in the worst case scenario. At each iteration, the computational work done is constant, meaning it does not depend on the size of k. Therefore, the upper bound of iterations is k, leading to a linear time complexity relative to the input value k.

Space Complexity

The space complexity of the code is O(1). The code uses a fixed amount of additional memory space regardless of the input size k, which includes variables n and i. Since the memory used does not scale with k, the space complexity is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫