首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各

2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各

作者头像
福大大架构师每日一题
发布于 2025-06-06 06:51:11
发布于 2025-06-06 06:51:11
7400
代码可运行
举报
运行总次数:0
代码可运行

2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各位数字的乘积能够被 t 整除。

1 <= n <= 100。

1 <= t <= 10。

输入:n = 15, t = 3。

输出:16。

解释:

16 的数位乘积为 6 ,可以被 3 整除,所以它是大于等于 15 且满足题目要求的最小整数。

题目来自力扣3345。

分步骤描述过程:

  1. 1. 问题理解
    • • 给定两个整数 nt,需要找到不小于 n 的最小整数,使得该整数的各位数字的乘积能被 t 整除。
    • • 例如,n = 15t = 3,需要找到 ≥15 的最小整数,其各位数字乘积能被 3 整除。15 的乘积是 1*5=5,不能被 3 整除;16 的乘积是 1*6=6,能被 3 整除,因此答案是 16
  2. 2. 算法思路
    • • 从 i = n 开始,逐个检查每个整数 i 是否满足条件。
    • • 对于每个 i,计算其各位数字的乘积:
      • • 初始化 prod = 1
      • • 通过循环取出 i 的每一位数字(从个位开始),并将 prod 乘以该数字。
    • • 检查 prod 是否能被 t 整除:
      • • 如果能,则返回当前的 i
      • • 如果不能,则继续检查 i+1
  3. 3. 具体步骤(以 n = 15t = 3 为例)
    • • 初始 i = 15
      • • 计算乘积:1 * 5 = 5
      • 5 % 3 = 2 ≠ 0,不满足。
    • i = 16
      • • 计算乘积:1 * 6 = 6
      • 6 % 3 = 0,满足条件,返回 16
  4. 4. 边界情况
    • • 如果 n = 0(但题目中 n ≥ 1,无需考虑)。
    • • 如果 t = 1,任何数字的乘积都能被 1 整除,直接返回 n
    • • 如果 n 本身已经满足条件(如 n = 12t = 21*2=2 能被 2 整除),直接返回 n
  5. 5. 终止条件
    • • 由于题目保证 nt 的范围较小(n ≤ 100t ≤ 10),算法一定会在有限步内终止。

时间复杂度和空间复杂度:

  • 时间复杂度
    • • 最坏情况下需要检查 O(M) 个数字,其中 M 是从 n 开始到第一个满足条件的数字的距离。
    • • 对于每个数字,计算其各位数字的乘积的时间复杂度是 O(d),其中 d 是数字的位数(最多 3 位,因为 n ≤ 100)。
    • • 因此,总时间复杂度是 O(M * d),可以认为是 O(M),因为 d 很小。
    • • 由于 nt 的范围很小,M 的最大值不会很大(例如,n = 99t = 10,需要检查到 100M = 2)。
  • 空间复杂度
    • • 只使用了常数级别的额外空间(如 prod、循环变量等),因此空间复杂度是 O(1)

Go完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
package main

import (
    "fmt"
)

func smallestNumber(n, t int)int {
    for i := n; ; i++ {
        prod := 1
        for x := i; x > 0; x /= 10 {
            prod *= x % 10
        }
        if prod%t == 0 {
            return i
        }
    }
}

func main() {
    n := 15
    t := 3
    result := smallestNumber(n, t)
    fmt.Println(result)
}

Python完整代码如下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# -*-coding:utf-8-*-

defsmallest_number(n, t):
    i = n
    whileTrue:
        prod = 1
        x = i
        while x > 0:
            prod *= x % 10
            x //= 10
        if prod % t == 0:
            return i
        i += 1

if __name__ == "__main__":
    n = 15
    t = 3
    result = smallest_number(n, t)
    print(result)
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2025-05-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。
福大大架构师每日一题
2025/06/06
550
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表
2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表示中,1 的个数与给定的“置位”数量相同。换句话说,x 的二进制中有指定数量的位是 1,且 x ≥ n,找到满足条件的最小的这样的 x。
福大大架构师每日一题
2025/06/19
770
2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表
2025-06-24:使两个整数相等的数位操作。用go语言,给定两个整数 n 和 m,它们的位数相同。 你可以对 n 执行任意次
2025-06-24:使两个整数相等的数位操作。用go语言,给定两个整数 n 和 m,它们的位数相同。 你可以对 n 执行任意次数的操作,每次操作都是以下两种之一:
福大大架构师每日一题
2025/06/24
550
2025-06-24:使两个整数相等的数位操作。用go语言,给定两个整数 n 和 m,它们的位数相同。 你可以对 n 执行任意次
2025-04-06:统计好整数的数目。用go语言,给定两个正整数 n 和 k,我们定义一个整数 x 为 k 回文整数的条件是:
2025-04-06:统计好整数的数目。用go语言,给定两个正整数 n 和 k,我们定义一个整数 x 为 k 回文整数的条件是:
福大大架构师每日一题
2025/04/06
1020
2025-04-06:统计好整数的数目。用go语言,给定两个正整数 n 和 k,我们定义一个整数 x 为 k 回文整数的条件是:
2025-04-28:替换为数位和以后的最小元素。用go语言,给定一个整数数组 nums,你需要将数组中每个元素替换成该元素各位
2025-04-28:替换为数位和以后的最小元素。用go语言,给定一个整数数组 nums,你需要将数组中每个元素替换成该元素各位数字之和。
福大大架构师每日一题
2025/04/28
1100
2025-04-28:替换为数位和以后的最小元素。用go语言,给定一个整数数组 nums,你需要将数组中每个元素替换成该元素各位
2024-11-16:哈沙德数。用go语言,如果一个整数能够被它的各个数位上数字的和整除, 我们称这个整数为哈沙德数(Harsh
2024-11-16:哈沙德数。用go语言,如果一个整数能够被它的各个数位上数字的和整除,
福大大架构师每日一题
2024/11/19
1500
2024-11-16:哈沙德数。用go语言,如果一个整数能够被它的各个数位上数字的和整除, 我们称这个整数为哈沙德数(Harsh
2025-04-03:统计近似相等数对Ⅱ。用go语言,你有一个正整数数组 nums。我们称两个整数 x 和 y 为“近似相等”,
2025-04-03:统计近似相等数对Ⅱ。用go语言,你有一个正整数数组 nums。我们称两个整数 x 和 y 为“近似相等”,如果我们可以对其中一个数执行至多两次操作,使得它们变得相等。这些操作包括选择 x 或 y 中的一个,交换这个数字的两个数位。
福大大架构师每日一题
2025/04/04
1060
2025-04-03:统计近似相等数对Ⅱ。用go语言,你有一个正整数数组 nums。我们称两个整数 x 和 y 为“近似相等”,
2025-07-18:最长乘积等价子数组。用go语言,给定一个只包含正整数的数组 nums。 定义:如果一个数组 arr 满足所
2025-07-18:最长乘积等价子数组。用go语言,给定一个只包含正整数的数组 nums。 定义:如果一个数组 arr 满足所有元素的乘积等于该数组最大公约数(GCD)与最小公倍数(LCM)的乘积,即
福大大架构师每日一题
2025/07/18
440
2025-07-18:最长乘积等价子数组。用go语言,给定一个只包含正整数的数组 nums。 定义:如果一个数组 arr 满足所
2025-03-29:找出最大的 N 位 K 回文数。用go语言,给定两个正整数 n 和 k。 一个正整数 x 被称为 k 回文
2025-03-29:找出最大的 N 位 K 回文数。用go语言,给定两个正整数 n 和 k。
福大大架构师每日一题
2025/03/29
1130
2025-03-29:找出最大的 N 位 K 回文数。用go语言,给定两个正整数 n 和 k。 一个正整数 x 被称为 k 回文
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
福大大架构师每日一题
2025/06/06
500
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整数 k。
福大大架构师每日一题
2025/07/08
600
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整
2025-06-03:检测相邻递增子数组Ⅱ。用go语言,给定一个包含 n 个整数的数组 nums,要求找出一个最大的整数 k,使
2025-06-03:检测相邻递增子数组Ⅱ。用go语言,给定一个包含 n 个整数的数组 nums,要求找出一个最大的整数 k,使得数组中存在两个连续且长度均为 k 的子数组,它们都是严格递增的。具体要求如下:
福大大架构师每日一题
2025/06/06
670
2025-06-03:检测相邻递增子数组Ⅱ。用go语言,给定一个包含 n 个整数的数组 nums,要求找出一个最大的整数 k,使
2025-04-01:统计近似相等数对Ⅰ。用go语言,给定一个正整数数组 nums,我们定义“近似相等”的一对数为:在下标 i
2025-04-01:统计近似相等数对Ⅰ。用go语言,给定一个正整数数组 nums,我们定义“近似相等”的一对数为:在下标 i 和 j(i < j)中,若能通过至多一次的操作使得 nums[i] 与 nums[j] 相等,我们称这对数是近似相等的。这个操作包括选择其中一个数,并交换它的两个数字位。请计算并返回这样的近似相等数对的数量。
福大大架构师每日一题
2025/04/01
1090
2025-04-01:统计近似相等数对Ⅰ。用go语言,给定一个正整数数组 nums,我们定义“近似相等”的一对数为:在下标 i
2024-12-11:数组最后一个元素的最小值。用go语言,给定两个整数 n 和 x,构造一个长度为 n 的正整数数组 nums
2024-12-11:数组最后一个元素的最小值。用go语言,给定两个整数 n 和 x,构造一个长度为 n 的正整数数组 nums,使得数组中相邻元素递增且所有元素按位与的结果为 x。返回可能的最小 nums 数组中的最后一个元素的值。
福大大架构师每日一题
2024/12/19
2570
2024-12-11:数组最后一个元素的最小值。用go语言,给定两个整数 n 和 x,构造一个长度为 n 的正整数数组 nums
2024-07-31:用go语言,给定两个正整数数组arr1和arr2,我们要找到属于arr1的整数x和属于arr2的整数y组成
2024-07-31:用go语言,给定两个正整数数组arr1和arr2,我们要找到属于arr1的整数x和属于arr2的整数y组成的所有数对(x, y)中,具有最长公共前缀的长度。
福大大架构师每日一题
2024/08/16
1760
2024-07-31:用go语言,给定两个正整数数组arr1和arr2,我们要找到属于arr1的整数x和属于arr2的整数y组成
2025-01-20:使所有元素都可以被 3 整除的最少操作数。用go语言,给定一个整数数组 nums,你可以通过对数组中任意一
2025-01-20:使所有元素都可以被 3 整除的最少操作数。用go语言,给定一个整数数组 nums,你可以通过对数组中任意一个元素进行加1或减1的操作。
福大大架构师每日一题
2025/01/22
970
2025-01-20:使所有元素都可以被 3 整除的最少操作数。用go语言,给定一个整数数组 nums,你可以通过对数组中任意一
2025-06-28:长度可被 K 整除的子数组的最大元素和。用go语言,给定一个整数数组 nums 和一个整数 k ,求 nu
2025-06-28:长度可被 K 整除的子数组的最大元素和。用go语言,给定一个整数数组 nums 和一个整数 k ,求 nums 中长度为 k 的倍数的非空子数组中,子数组和的最大值。返回该最大和。
福大大架构师每日一题
2025/06/28
460
2025-06-28:长度可被 K 整除的子数组的最大元素和。用go语言,给定一个整数数组 nums 和一个整数 k ,求 nu
2025-01-01:优质数对的总数Ⅰ。用go语言,给定两个整数数组 nums1 和 nums2,分别长度为 n 和 m,以及一
2025-01-01:优质数对的总数Ⅰ。用go语言,给定两个整数数组 nums1 和 nums2,分别长度为 n 和 m,以及一个正整数 k。
福大大架构师每日一题
2025/01/02
1160
2025-01-01:优质数对的总数Ⅰ。用go语言,给定两个整数数组 nums1 和 nums2,分别长度为 n 和 m,以及一
2025-06-19:识别数组中的最大异常值。用go语言,你有一个长度为 n 的整数数组 nums,其中恰好有 n-2 个元素属
2025-06-19:识别数组中的最大异常值。用go语言,你有一个长度为 n 的整数数组 nums,其中恰好有 n-2 个元素属于“特殊数字”类别。剩下的两个元素中,一个等于所有这些特殊数字的总和,另一个是一个“异常值”。
福大大架构师每日一题
2025/06/19
820
2025-06-19:识别数组中的最大异常值。用go语言,你有一个长度为 n 的整数数组 nums,其中恰好有 n-2 个元素属
2025-04-16:找到稳定山的下标。用go语言,给定一个整数数组 height,表示一列山的高度,其中 height[i]
2025-04-16:找到稳定山的下标。用go语言,给定一个整数数组 height,表示一列山的高度,其中 height[i] 表示第 i 座山的高度,还有一个整数 threshold。我们定义一个山为“稳定”的条件是:对于每座下标不为 0 的山,如果它左侧相邻的山的高度严格大于 threshold,那么这座山就是稳定的。而下标为 0 的山永远被认为不稳定。
福大大架构师每日一题
2025/04/16
620
2025-04-16:找到稳定山的下标。用go语言,给定一个整数数组 height,表示一列山的高度,其中 height[i]
推荐阅读
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
550
2025-06-18:仅含置位位的最小整数。用go语言,给定一个正整数 n,求一个不小于 n 的最小整数 x,且该整数的二进制表
770
2025-06-24:使两个整数相等的数位操作。用go语言,给定两个整数 n 和 m,它们的位数相同。 你可以对 n 执行任意次
550
2025-04-06:统计好整数的数目。用go语言,给定两个正整数 n 和 k,我们定义一个整数 x 为 k 回文整数的条件是:
1020
2025-04-28:替换为数位和以后的最小元素。用go语言,给定一个整数数组 nums,你需要将数组中每个元素替换成该元素各位
1100
2024-11-16:哈沙德数。用go语言,如果一个整数能够被它的各个数位上数字的和整除, 我们称这个整数为哈沙德数(Harsh
1500
2025-04-03:统计近似相等数对Ⅱ。用go语言,你有一个正整数数组 nums。我们称两个整数 x 和 y 为“近似相等”,
1060
2025-07-18:最长乘积等价子数组。用go语言,给定一个只包含正整数的数组 nums。 定义:如果一个数组 arr 满足所
440
2025-03-29:找出最大的 N 位 K 回文数。用go语言,给定两个正整数 n 和 k。 一个正整数 x 被称为 k 回文
1130
2025-06-05:统计小于 N 的 K 可约简整数。用go语言,给定一个二进制字符串 s,它表示一个整数 n 的二进制形式。
500
2025-07-05:统计异或值为给定值的路径数目。用go语言,给定一个大小为 m 行 n 列的二维整数数组 grid 和一个整
600
2025-06-03:检测相邻递增子数组Ⅱ。用go语言,给定一个包含 n 个整数的数组 nums,要求找出一个最大的整数 k,使
670
2025-04-01:统计近似相等数对Ⅰ。用go语言,给定一个正整数数组 nums,我们定义“近似相等”的一对数为:在下标 i
1090
2024-12-11:数组最后一个元素的最小值。用go语言,给定两个整数 n 和 x,构造一个长度为 n 的正整数数组 nums
2570
2024-07-31:用go语言,给定两个正整数数组arr1和arr2,我们要找到属于arr1的整数x和属于arr2的整数y组成
1760
2025-01-20:使所有元素都可以被 3 整除的最少操作数。用go语言,给定一个整数数组 nums,你可以通过对数组中任意一
970
2025-06-28:长度可被 K 整除的子数组的最大元素和。用go语言,给定一个整数数组 nums 和一个整数 k ,求 nu
460
2025-01-01:优质数对的总数Ⅰ。用go语言,给定两个整数数组 nums1 和 nums2,分别长度为 n 和 m,以及一
1160
2025-06-19:识别数组中的最大异常值。用go语言,你有一个长度为 n 的整数数组 nums,其中恰好有 n-2 个元素属
820
2025-04-16:找到稳定山的下标。用go语言,给定一个整数数组 height,表示一列山的高度,其中 height[i]
620
相关推荐
2025-06-02:最小可整除数位乘积Ⅱ。用go语言,给定一个表示正整数的字符串 num 和一个整数 t。 定义:如果一个整数
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档