Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1015.html

1015. Smallest Integer Divisible by K

Level

Medium

Description

Given a positive integer K, you need find 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.

Example 1:

Input: 1

Output: 1

Explanation: The smallest answer is N = 1, which has length 1.

Example 2:

Input: 2

Output: -1

Explanation: There is no such positive integer N divisible by 2.

Example 3:

Input: 3

Output: 3

Explanation: The smallest answer is N = 111, which has length 3.

Note:

  • 1 <= K <= 10^5

Solution

If K is a multiple of 2 or 5, then any number divisible by K can’t end with 1, so return -1.

Otherwise, each time append a 1 to the current number (which is initially 0) and check whether the new number is divisible by K. Use modulo operation to avoid overflow.

  • class Solution {
    public int smallestRepunitDivByK(int K) {
        if (K % 2 == 0 || K % 5 == 0)
            return -1;
        int value = 1;
        int length = 1;
        while (value % K != 0) {
            value = value % K * 10 + 1;
            length++;
        }
        return length;
    }
}

  • // OJ: https://leetcode.com/problems/smallest-integer-divisible-by-k/
// Time: O(K)
// Space: O(K)
class Solution {
public:
    int smallestRepunitDivByK(int k) {
        unordered_set<int> s;
        for (int n = 1 % k, len = 1; true; n = (n * 10 + 1) % k, ++len) {
            if (n == 0) return len;
            if (s.count(n)) return -1;
            s.insert(n);
        }
    }
};

  • # 1015. Smallest Integer Divisible by K
# https://leetcode.com/problems/smallest-integer-divisible-by-k/

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 and k % 5 == 0: return -1
        mod_set = set()
        prev = 0
        
        for i in range(1, k + 1):
            prev = (prev * 10 + 1) % k
            if prev == 0: return i
            if prev in mod_set: return -1
            mod_set.add(prev)
        
        return -1


  • func smallestRepunitDivByK(k int) int {
	n := 1 % k
	for i := 1; i <= k; i++ {
		if n == 0 {
			return i
		}
		n = (n*10 + 1) % k
	}
	return -1
}

  • function smallestRepunitDivByK(k: number): number {
    let n = 1 % k;
    for (let i = 1; i <= k; ++i) {
        if (n === 0) {
            return i;
        }
        n = (n * 10 + 1) % k;
    }
    return -1;
}

All Problems

All Solutions