【1015. 可被 K 整除的最小整数】

这篇具有很好参考价值的文章主要介绍了【1015. 可被 K 整除的最小整数】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

来源:力扣(LeetCode)

描述:

给定正整数 k ,你需要找出可以被 k 整除的、仅包含数字 1 的最 正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ,就返回 -1

注意: n 不符合 64 位带符号整数。

示例 1:

输入:k = 1
输出:1
解释:最小的答案是 n = 1,其长度为 1

示例 2:

输入:k = 2
输出:-1
解释:不存在可被 2 整除的正整数 n 。

示例 3:

输入:k = 3
输出:3
解释:最小的答案是 n = 111,其长度为 3

提示:

  • 1 <= k <= 105

方法:遍历

思路与算法

题目要求出长度最小的仅包含的 1 的并且被 k 整除的正整数。我们从 n = 1 开始枚举,此时对 k 取余得余数 resid = 1 mod k。如果 resid 不为 0,则表示 n 当前还不能被 k 整除,我们需要增加 n 的长度。令 nnew = nold ×10 + 1,residnew = nnew mod k 。将 nold 代入其中可得:

【1015. 可被 K 整除的最小整数】

从上式可以发现,新的余数 residnew 可以由 residold 推导得到。因此在遍历过程中不需要记录 n,只需记录 resid。由于 resid 是对 k 取余之后的余数,因此种类数不会超过 k。

在遍历过程中如果出现重复的 resid,表示遇到了一个循环,接着遍历下去会重复循环中的每一步,不会产生新的余数。所以我们用一个哈希表记录出现过的余数,当更新 resid 后发现该值已经在哈希表时,直接返回 −1。否则我们一直遍历,直到 resid 变为 0。最终哈希表中的元素个数或者遍历次数就是实际 n 的长度。

代码:

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int resid = 1 % k, len = 1; // resid为余数,len为数字长度,初始值为1
        unordered_set<int> st; // 创建一个无序集合,用于存储余数
        st.insert(resid); // 插入余数1
        while (resid != 0) { // 当余数为0时退出循环
            resid = (resid * 10 + 1) % k; // 计算下一个余数
            len++; // 数字长度+1
            if (st.find(resid) != st.end()) { // 如果余数重复出现,则无解
                return -1;
            }
            st.insert(resid); // 将余数插入集合
        }
        return len; // 返回数字长度
    }
};

优化

注意到当 k 为 2 或者 5 的倍数时,能够被 k 整除的数字末尾一定不为 1,所以此时一定无解。

那当 k 不为 2 或者 5 的倍数时一定有解吗?我们做进一步的分析。

resid 随着 1 的增加,最后一定进入循环,我们能找到两个对 k 同余的 n 和 m。假设 n > m,那么一定有以下等式成立:

(n − m) ≡ 0 (mod k)

n − m 可以表示为 11…100…0 的形式,因此有 11 … 100 … 0 ≡ 0(mod k)。

如果此时 k 不为 2 或 5 的倍数,则 k 与 10 没有公因数,k 与 10 互质。n − m 末尾的 0 可以除掉,因此 11…1 ≡ 0(mod k),问题一定有解。

代码:

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        // 若 k 能被 2 或 5 整除,则无解,返回 -1
        if (k % 2 == 0 || k % 5 == 0) {
            return -1;
        }
        // 初始化余数为 1,表示一个数的最低位是 1
        int resid = 1 % k, len = 1;
        // 若余数不为 0,继续迭代
        while (resid != 0) {
            // 计算下一个数的余数,下一个数在当前余数后加一个 1
            resid = (resid * 10 + 1) % k;
            len++;
        }
        // 返回数字 1 的最小重复次数
        return len;
    }
};

执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:5.7 MB, 在所有 C++ 提交中击败了93.94%的用户
复杂度分析
时间复杂度:O(k)。过程中最多会遍历 k 次。
空间复杂度:O(1)。如果使用哈希表,空间复杂度为 O(k)。
author:LeetCode-Solution文章来源地址https://www.toymoban.com/news/detail-437966.html

到了这里,关于【1015. 可被 K 整除的最小整数】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【1262. 可被三整除的最大和】

    来源:力扣(LeetCode) 描述: 给你一个整数数组 nums ,请你找出并返回能被三整除的元素最大和。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 4 * 10 4 1 = nums[i] = 10 4 方法:贪心 + 正向思维 我们把数组中的数分成三部分 a, b, c,它们分别包含所有被 3 除余 0 , 1, 2 的数。显

    2024年02月10日
    浏览(37)
  • 和可被K整除的子数组(Java详解)

    目录 一、题目描述 二、题解 思路分析 具体实现 完整代码 给定一个整数数组  nums  和一个整数  k  ,返回其中元素之和可被  k  整除的(连续、非空)  子数组  的数目。 子数组  是数组的  连续  部分。 示例: 输入:nums = [4,5,0,-2,-3,1],k = 5 输出:7 输入:nums = [ 5 ],

    2024年02月01日
    浏览(36)
  • 【每日一题Day199】LC1010总持续时间可被 60 整除的歌曲 | 哈希表

    总持续时间可被 60 整除的歌曲【LC1010】 在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。 返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望下标数字 i 和 j 满足 i j 且有 (time[i] + time[j]) % 60 == 0 。 思路 由于需要求两首歌的总时间可被60整除

    2024年02月03日
    浏览(43)
  • [Algorithm][前缀和][和为K的子数组][和可被K整除的子数组][连续数组][矩阵区域和]详细讲解

    和为 K 的子数组 分析 :因为有 负数 的存在 无法使用\\\" 双指针 \\\"优化,因为 区间求和不具备单调性 可能已经找到前缀和为k的子数组了,但是后面仍然可能会有更长的和为k的子数组存在 思路 :前缀和 + 哈希表 前缀和 : 以 i 位置为结尾 的所有的子数组 将问题转化为 :在

    2024年04月28日
    浏览(33)
  • 算法——前缀和之除自身以外数组的乘积、和为K的子数组、和可被K整除的子数组、连续数组、矩阵区域和

    这几道题对于我们前面讲过的一维、二维前缀和进行了运用,包含了面对特殊情况的反操作 目录 4.除自身以外数组的乘积 4.1解析 4.2题解 5.和为K的子数组 5.1解析 5.2题解 6.和可被K整除的子数组 6.1解析 6.2题解 7.连续数组 7.1题解 7.2题解 8.矩阵区域和 8.1解析 8.2题解 4.除自身以外

    2024年04月14日
    浏览(44)
  • 力扣(leetcode)第599题两个列表的最小索引总和(Python)

    题目链接:599.两个列表的最小索引总和 假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。

    2024年01月23日
    浏览(43)
  • leetcode(力扣) 76. 最小覆盖子串 (滑动窗口,超详细问答版解析)

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是

    2024年02月08日
    浏览(52)
  • 【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)

    目录 1、题目介绍 2、解题思路 2.1、优先队列解法 2.2、top-k问题解法 原题链接: 面试题 17.14. 最小K个数 - 力扣(LeetCode)  题目要求非常简短,也非常简单,就是求一组数中的k个最小数。         如果在正常刷题过程中遇到这种题,那么这道题毋庸置疑是秒杀题,使用最

    2024年01月25日
    浏览(42)
  • 算法学习——LeetCode力扣补充篇11(64. 最小路径和、48. 旋转图像 、169. 多数元素、394. 字符串解码、240. 搜索二维矩阵 II )

    64. 最小路径和 - 力扣(LeetCode) 描述 给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 示例 1: 输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→

    2024年04月23日
    浏览(38)
  • 力扣:罗马转整数

    class 定义了一个类Solution,这个类里面有有私有成员和共有成员 首先定义了一个私有成员,我也不知道为什么需要这个私有成员,unordered_mapunordered_mapchar, int用法再去搜搜。 注意两个头文件不要加h。 代码整体的思路就是定义一个类,这个类首先定义了私有对象一个map的字符到

    2024年02月06日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包