1015. Smallest Integer Divisible by K

[mah-shamim]

Topics: Hash Table, Math, Weekly Contest 129

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.

Note: n may not fit in a 64-bit signed integer.

Example 1:

• Input: k = 1
• Output: 1
• Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

• Input: k = 2
• Output: -1
• Explanation: There is no such positive integer n divisible by 2.

Example 3:

• Input: k = 3
• Output: 3
• Explanation: The smallest answer is n = 111, which has length 3.

Constraints:

• 1 <= k <= 10⁵

Hint:

1. 11111 = 1111 * 10 + 1 We only need to store remainders modulo K.
2. If we never get a remainder of 0, why would that happen, and how would we know that?

[mah-shamim]

We need to find the smallest number consisting only of digit '1' that is divisible by k.

Approach:

• I can't actually build the number because it might be extremely large
• Instead, I can work with remainders and build the number digit by digit
• The number n can be represented as: n = 1, 11, 111, 1111, etc.
• Each new number is the previous number × 10 + 1

Let's implement this solution in PHP: 1015. Smallest Integer Divisible by K

<?php
/**
 * @param Integer $k
 * @return Integer
 */
function smallestRepunitDivByK($k) {
    // If k is even or divisible by 5, no solution exists
    // because numbers ending with 1 can't be divisible by 2 or 5
    if ($k % 2 == 0 || $k % 5 == 0) {
        return -1;
    }

    $remainder = 0;

    // Try up to k iterations - if we don't find 0 by then, it doesn't exist
    for ($length = 1; $length <= $k; $length++) {
        // Build the number: remainder = (remainder * 10 + 1) % k
        $remainder = ($remainder * 10 + 1) % $k;

        // If remainder becomes 0, we found our answer
        if ($remainder == 0) {
            return $length;
        }
    }

    return -1;
}

// Test cases
echo smallestRepunitDivByK(1) . "\n";   // Output: 1
echo smallestRepunitDivByK(2) . "\n";   // Output: -1
echo smallestRepunitDivByK(3) . "\n";   // Output: 3
?>

Explanation:

1. Early termination for impossible cases: If k is even or divisible by 5, no number ending with digit 1 can be divisible by it, so we return -1 immediately.

2. Working with remainders: Instead of building the actual number (which could be huge), I track only the remainder when divided by k. This keeps the numbers manageable.

3. Building the sequence:

   • Start with remainder = 0
   • For each new digit '1' we add: new_remainder = (old_remainder × 10 + 1) % k
   • This is equivalent to building: 1, 11, 111, 1111, etc.

4. Stopping condition:

   • If remainder becomes 0, we found our answer
   • If we try k iterations without finding 0, no solution exists (by pigeonhole principle)

Why the loop runs at most k times?

• There are only k possible remainders (0 to k-1)
• If we don't hit 0 after k iterations, we must have repeated a remainder
• Once we repeat a remainder, we're in a cycle and will never hit 0

Example walkthrough for k = 3:

• length = 1: remainder = (0×10 + 1) % 3 = 1
• length = 2: remainder = (1×10 + 1) % 3 = 11 % 3 = 2
• length = 3: remainder = (2×10 + 1) % 3 = 21 % 3 = 0 ✓
• Return 3

This solution runs in O(k) time and O(1) space, which is efficient for the given constraints (k ≤ 10⁵).

[basharul-siddike]

Thanks for solving the problem of "Smallest Integer Divisible by K"

[mah-shamim]

Thanks