Welcome to Subscribe On Youtube

1015. Smallest Integer Divisible by K

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.

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 <= 105

Solutions

  • class Solution {
        public int smallestRepunitDivByK(int k) {
            int n = 1 % k;
            for (int i = 1; i <= k; ++i) {
                if (n == 0) {
                    return i;
                }
                n = (n * 10 + 1) % k;
            }
            return -1;
        }
    }
    
  • class Solution {
    public:
        int smallestRepunitDivByK(int k) {
            int n = 1 % k;
            for (int i = 1; i <= k; ++i) {
                if (n == 0) {
                    return i;
                }
                n = (n * 10 + 1) % k;
            }
            return -1;
        }
    };
    
  • class Solution:
        def smallestRepunitDivByK(self, k: int) -> int:
            n = 1 % k
            for i in range(1, k + 1):
                if n == 0:
                    return i
                n = (n * 10 + 1) % k
            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