Сложность: medium
Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.
Пример:
Input: k = 1
Output: 1
👨💻 Алгоритм:
1⃣Использование остатка для нахождения числа с цифрами 1:
Создайте переменную num и установите ее равной 1.
Создайте переменную length и установите ее равной 1 для отслеживания длины числа.
2⃣Итеративное нахождение числа:
Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.
Увеличивайте length на 1 в каждой итерации.
Если в какой-то итерации num % k == 0, верните length.
3⃣Проверка бесконечного цикла:
Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует.
😎 Решение:
class Solution {
public:
int smallestRepunitDivByK(int k) {
int num = 1, length = 1;
unordered_set<int> seen;
while (num % k != 0) {
if (seen.count(num % k)) {
return -1;
}
seen.insert(num % k);
num = (num * 10 + 1) % k;
length++;
}
return length;
}
};Ставь 👍 и забирай 📚 Базу знаний