1015. Smallest Integer Divisible by K

leetcode medium

#bit-manipulation#csharp#hash-table#leetcode#math#medium

Task

Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.

Пример:

Input: k = 1

Output: 1

C# solution

matched/original

public class Solution {
    public int SmallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        HashSet<int> seen = new HashSet<int>();
        
        while (num % k != 0) {
            if (seen.Contains(num % k)) {
                return -1;
            }
            seen.Add(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SmallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        HashSet<int> seen = new HashSet<int>();
        
        while (num % k != 0) {
            if (seen.Contains(num % k)) {
                return -1;
            }
            seen.push_back(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

Java solution

matched/original

public class Solution {
    public int smallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        Set<Integer> seen = new HashSet<>();
        
        while (num % k != 0) {
            if (seen.contains(num % k)) {
                return -1;
            }
            seen.add(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

JavaScript solution

matched/original

class Solution {
    smallestRepunitDivByK(k) {
        let num = 1, length = 1;
        let seen = new Set();
        
        while (num % k !== 0) {
            if (seen.has(num % k)) {
                return -1;
            }
            seen.add(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}

Python solution

matched/original

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        num, length = 1, 1
        seen = set()
        
        while num % k != 0:
            if num % k in seen:
                return -1
            seen.add(num % k)
            num = (num * 10 + 1) % k
            length += 1
        
        return length

Go solution

matched/original

func smallestRepunitDivByK(k int) int {
    num, length := 1, 1
    seen := make(map[int]bool)
    
    for num % k != 0 {
        if seen[num % k] {
            return -1
        }
        seen[num % k] = true
        num = (num * 10 + 1) % k
        length++
    }
    
    return length
}

Explanation

Algorithm

Использование остатка для нахождения числа с цифрами 1:

Создайте переменную num и установите ее равной 1.

Создайте переменную length и установите ее равной 1 для отслеживания длины числа.

Итеративное нахождение числа:

Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.

Увеличивайте length на 1 в каждой итерации.

Если в какой-то итерации num % k == 0, верните length.

Проверка бесконечного цикла: