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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest Integer Divisible by K

Number: 1064

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a positive integer k, find the length of the smallest positive integer n such that n is divisible by k and n consists only of the digit 1. If no such n exists, return -1.

Key Insights

  • The number n is built solely from the digit '1', making it a repunit number.
  • Direct construction of n is infeasible due to its potential size. Instead, use modulo arithmetic to only track remainders.
  • Repeatedly update the remainder by computing (previous_remainder * 10 + 1) mod k.
  • If the remainder becomes 0, the current length is the answer.
  • If a remainder repeats (cycle detected), return -1 because no divisible repunit exists.

Space and Time Complexity

Time Complexity: O(k) - At most k iterations
Space Complexity: O(k) - In the worst-case storing up to k remainders

Solution

We use modulo arithmetic to avoid constructing large numbers. Starting with the remainder of 1 mod k, we iteratively update the remainder by appending the digit '1'. At each iteration, if the remainder is zero, we return the count of digits. We use a set to record seen remainders to detect cycles. This prevents infinite loops if no valid number exists. This technique efficiently determines the length of the smallest repunit divisible by k without handling enormously large integers.

Code Solutions

# Python solution with line-by-line comments
def smallestRepunitDivByK(k):
    # Compute the remainder of '1' divided by k
    remainder = 1 % k
    # If the initial remainder is zero, return length 1
    if remainder == 0:
        return 1
    # Initialize length of repunit and a set to track seen remainders
    length = 1
    seen_remainders = {remainder}
    
    # Loop until a valid repunit is found or a cycle is detected
    while True:
        length += 1
        # Update the remainder by appending another '1'
        remainder = (remainder * 10 + 1) % k
        # Check if the new number is divisible by k
        if remainder == 0:
            return length
        # If we have seen this remainder before, a cycle exists; no solution
        if remainder in seen_remainders:
            return -1
        seen_remainders.add(remainder)

# Example usage:
print(smallestRepunitDivByK(3))  # Expected output: 3
← Back to All Questions