最小偶倍数

标签: 数学 数论

难度: Easy

给你一个正整数 n ,返回 2 n 的最小公倍数(正整数)。

示例 1:

输入:n = 5
输出:10
解释:5 和 2 的最小公倍数是 10 。

示例 2:

输入:n = 6
输出:6
解释:6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。

提示:

  • 1 <= n <= 150

Submission

运行时间: 16 ms

内存: 16.0 MB

class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        if n % 2 == 0 :
            return n
        elif n == 1 :
            return 2
        else:
            return 2 * n    

Explain

此题解的思路基于计算2和n的最小公倍数(LCM)。当n是偶数时,n本身就是2和n的最小公倍数,因为所有偶数都由2整除,所以返回n。当n是奇数时,n和2的最小公倍数是它们的乘积,即2*n,因为2和奇数没有其他公因数。特别地,当n为1时,虽然1*2也是2,但代码中单独处理了这种情况,直接返回2。

时间复杂度: O(1)

空间复杂度: O(1)

# 定义解决方案类

class Solution:
    def smallestEvenMultiple(self, n: int) -> int:
        # 如果n是偶数,直接返回n
        if n % 2 == 0 :
            return n
        # 如果n是1,特殊处理,返回2
        elif n == 1 :
            return 2
        # 如果n是奇数,返回2和n的乘积
        else:
            return 2 * n

Explore

在n为1的情况下,按照奇数的一般处理逻辑,2*n的结果确实是2。特殊处理n=1的目的可能是为了强调1的独特性或减少计算步骤。实际上,对于n=1来说,2*n和直接返回2的结果是一样的,所以这种特殊处理更多的是代码的风格选择或是为了代码的清晰性。

确实存在一种更通用的方法来计算两个数的最小公倍数,即利用最大公约数(Greatest Common Divisor, GCD)。最小公倍数可以通过公式 (a * b) / GCD(a, b) 计算。在Python中,可以使用math库中的gcd函数来找出两个数的最大公约数,然后应用此公式。这种方法可以避免分情况讨论奇偶性,对任意两个整数都适用。

题解中没有专门处理极大值(如n=150)的原因是因为算法本身在处理最小公倍数时具有普适性和数学上的正确性。无论n的值如何,只要遵循奇数和偶数的处理逻辑,结果都是正确的。此题解假设输入值n始终在合理范围内(例如1到150),并且在这个范围内,计算机处理乘法和取模运算都是安全的。

是的,代码中没有添加异常处理意味着它假设所有输入都符合题目给定的条件1 <= n <= 150。在实际应用中,如果存在输入超出这个范围或者输入类型错误的可能性,应该加入相应的异常处理或验证逻辑来确保代码的健壮性和错误处理能力。