最小偶倍数

题目

---

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 150

分析题目

给定一个数，找出这个数的最小公倍数。
题目很好理解， 如示例中：2, 5 的最小公倍数是 10, 2, 6 的公倍数是 6。

方法1：循环遍历

---

思路

如果 n 与 2 之间没有公约数，那么最小公倍数一定是n*2, 所以只要循环 [2..n * 2] 中的元素，那么一定可以找到最小公倍数

具体实现

Java 实现

class Solution {
    public int smallestEvenMultiple(int n) {
        for(int i = 2; i <= n * 2; i+=2) {
            if(i % n == 0) return i;
        }
        return 0;
    }
}

JavaScript 实现

var smallestEvenMultiple = function(n) {
    for(let i = 2; i <= n * 2; i+=2){
        if(i % n == 0) return i;
    }
};

复杂度分析

• 时间复杂度：$O(n)$ 其中 n 是输入的大小，因为每次都 +2，所以虽然遍历范围是[2..n*2],但也只需要循环 n 次
• 空间复杂度：$O(1)$ 只需要一个变量记录当前 index 即可。

方法2： 数学

思路

对于任意两个正整数 $n$, $m$ 的最小公倍数为 $\frac {n\times m} {gcd(n,m)}$ , 其中 $gcd(n,m)$ 为 $n$ 和 $m$ 最大公约数。
现在题目给出一个正整数 $n$，需要返回 2 和 $n$ 的最小公倍数，又因为任意正偶数与 2 的最大公约数为 2，任意整奇数的最大公约数为 1。所以当 $n$ 为偶数时直接返回 $n$, 否则返回 $n \times 2$ 即可。

• gcd 求最大公约数： 欧几里得算法

具体实现

Java 实现

class Solution {
 public int smallestEventMultiple(int n) {
  return n % 2 == 0 ? n : 2 * n;
 }
}

JavaScript 实现

var smallestEvenMultiple = function(n) { 
 return n % 2 == 0 ? n : n * 2; 
};

方法3： 位运算

思路

基于 方法2： 数学 的思路，我们通过位运算再次简化代码。
通过 n & 1 确定 n 奇偶性，方法等价于 n % 2 , 如果结果为 0 则说明是偶数，否则是奇数。

通过左移运维算的操作将 n 向左移动 1 位或 0 位。如果 n 是偶数，则 n << (n & 1) 的结果等于将 n 向左移动 0 位，结果仍然等于 n。如果 n 是奇数，则n << (n & 1) 的结果等于将 n 向左移动 1 位，结果等于 n * 2。

因此，n << (n & 1) 的结果等于将一个奇数 n 乘以 2，或者保持一个偶数 n 不变。

代码实现

Java 实现

class Solution {
 public int smallestEventMultiple(int n) {
  return n << (n & 1);
 }
}

JavaScript 实现

var smallestEvenMultiple = function(n) { 
 return n << (n & 1);
};