Smallest Integer Divisible By K - Leetcode Solution

Problem Statement:

Given a positive integer K, you need to find the smallest positive integer N such that N is divisible by K, N only contains the digit 1.

Example 1:

Input: K = 1 Output: 1 Explanation: The smallest positive integer divisible by 1 is 1 itself.

Example 2:

Input: K = 3 Output: 3 Explanation: The smallest positive integer divisible by 3 is 111.

Example 3:

Input: K = 7 Output: 7 Explanation: The smallest positive integer divisible by 7 is 1111111.

Example 4:

Input: K = 2 Output: -1 Explanation: There is no such positive integer that exists which is divisible by 2 and only contains the digit 1.

Approach:

The problem asks to find the smallest positive integer N such that N is divisible by K, and N contains only the digit 1. Such numbers are also known as repunit numbers. A brute-force approach would be to start from 1 and keep incrementing the number by 1 until we find a number that is divisible by K and contains only the digit 1. But this approach would not work for large values of K.

We can use the observation that if K shares a common factor with 10, then there is no repunit that is divisible by K. That is because a repunit N with n digits can be written as (10^n - 1) / 9. If K shares a common factor with 10, then K has a factor of 2 or 5 in its prime factorization, which means (10^n - 1) / 9 is not divisible by K.

Therefore, we will first check whether K shares a common factor with 10. If it does, we return -1. Otherwise, we will generate repunits of increasing length until we find a repunit that is divisible by K. To generate a repunit of length n, we calculate (10^n - 1) / 9. We can observe that since (10^p - r) % p = 0 if and only if r is the remainder of 10^p modulo p, we only need to keep track of the remainder at each step. If the remainder is 0, we have found the repunit that is divisible by K.

Algorithm:

1. If K shares a common factor with 10, return -1.
2. Initialize a variable r = 0 to keep track of the remainder.
3. For each repunit length n starting from 1, calculate r = (r * 10 + 1) % K.
4. If r == 0, we have found the repunit that is divisible by K. Return the length n.
5. If we have generated a repunit of length K without finding a divisible one, return -1.

Code:

Java:

class Solution { public int smallestRepunitDivByK(int K) { if (K % 2 == 0 || K % 5 == 0) { return -1; } int r = 0; for (int n = 1; n <= K; n++) { r = (r * 10 + 1) % K; if (r == 0) { return n; } } return -1; } }

Python:

class Solution: def smallestRepunitDivByK(self, K: int) -> int: if K % 2 == 0 or K % 5 == 0: return -1 r = 0 for n in range(1, K + 1): r = (r * 10 + 1) % K if r == 0: return n return -1

1