1015. Smallest Integer Divisible by K

题目信息

题号:

1015

难度:

Medium

主题:

整除、十进制构造、最短长度

原题:

LeetCode 1015

重点:

目标正整数的十进制表示只能由数字 1 组成;返回最短表示长度而不是整数本身,不存在时返回 -1

题目重述

给定正整数 k。在正整数 1、11、111、……中,寻找能够被 k 整除的最小整数。这些候选数的十进制表示只包含数字 1。

请返回该最小整数的十进制位数。若不存在任何只由 1 组成且能被 k 整除的正整数,返回 -1。

1 <= k <= 10^5。

自建示例

最短可整除数包含六个数字:

输入:k = 7
输出:6
解释:111111 能被 7 整除,而 1、11、111、1111 和 11111 都不能,因此最短长度为 6。

偶数因子不可能整除候选数:

输入:k = 2
输出:-1
解释:所有候选数的末位都是 1,因此全部为奇数,不可能被 2 整除。