We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Integer Divisible by K

Difficulty: Medium

Problem Description

Given a positive integer k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1. Return the length of n. If there is no such n, return -1.

Key Insights

  • The integer n can be represented as a series of the digit '1' (e.g., 1, 11, 111, etc.).
  • A number composed only of the digit '1' can be expressed in the form of (10^length - 1)/9 for a given length.
  • The problem can be solved using modular arithmetic to avoid large number computations.
  • To find n, we can use a breadth-first search (BFS) approach to explore numbers formed by adding '1' to the previous numbers until we find one that is divisible by k.

Space and Time Complexity

Time Complexity: O(k) - In the worst case, we may need to check up to k different remainders. Space Complexity: O(k) - We may store up to k different states in a queue for BFS.

Solution

To solve the problem, we employ a breadth-first search (BFS) approach, where we generate numbers made up of the digit '1' and check their divisibility by k. We utilize a queue to keep track of the current number in string form and its corresponding length. We also use a set to keep track of the remainders we have already seen to avoid cycles.

Code Solutions

from collections import deque

def smallestRepunitDivByK(k):
    if k % 2 == 0 or k % 5 == 0:
        return -1  # Numbers with only 1s cannot be divisible by even numbers or multiples of 5
    
    queue = deque([(1, 1)])  # (current number's remainder, length of the number)
    visited = set()  # To track visited remainders

    while queue:
        remainder, length = queue.popleft()
        
        if remainder % k == 0:
            return length
        
        # Calculate the next number
        next_remainder = (remainder * 10 + 1) % k
        
        if next_remainder not in visited:
            visited.add(next_remainder)
            queue.append((next_remainder, length + 1))
    
    return -1
← Back to All Questions