n, return the smallest positive integer that is a multiple of both 2 and n.
Example 1:
Input: n = 5 Output: 10 Explanation: The smallest multiple of both 5 and 2 is 10.
Example 2:
Input: n = 6 Output: 6 Explanation: The smallest multiple of both 6 and 2 is 6. Note that a number is a multiple of itself.
Constraints:
1 <= n <= 150Problem Overview: Given a positive integer n, return the smallest positive number that is both a multiple of n and an even number. In other words, compute the smallest even number divisible by n. This is essentially finding LCM(n, 2).
The key observation is simple: if n is already even, then n itself satisfies the condition. If n is odd, multiplying it by 2 produces the smallest even multiple.
Approach 1: Multiply and Check (O(1) time, O(1) space)
This approach relies on a basic property from math and number theory. The smallest even multiple of n is equivalent to the least common multiple of n and 2. Instead of explicitly computing LCM, you check whether n is even using the modulo operation. If n % 2 == 0, return n. Otherwise return 2 * n.
This works because any even number already contains the factor 2, meaning it is automatically divisible by both n and 2. If n is odd, the smallest number that includes both factors is simply 2n. The algorithm performs a single arithmetic check and multiplication, giving constant time complexity O(1) and constant space O(1). This is the most straightforward and readable implementation.
Approach 2: Bit Manipulation (O(1) time, O(1) space)
You can also determine whether n is even using bit manipulation. In binary representation, even numbers always end with 0 while odd numbers end with 1. Using the expression n & 1 extracts the least significant bit.
If (n & 1) == 0, the number is even and you return n. Otherwise return n * 2. This avoids the modulo operator and relies purely on bitwise operations. The runtime remains O(1) because only a single bit check and multiplication occur, and memory usage is also O(1).
This approach is common in performance-sensitive code and demonstrates familiarity with binary representations of integers. While the performance difference is negligible for this problem, bitwise checks are often faster at the machine level.
Recommended for interviews: The modulo-based solution is typically what interviewers expect first because it directly reflects the mathematical insight behind the problem. Mentioning that the result is LCM(n, 2) shows strong understanding of number theory. The bit manipulation version is a good follow-up optimization that demonstrates deeper familiarity with low-level integer operations.
This approach involves calculating the smallest number that results from multiplying n such that it is also even. Since the problem requires a number that's a multiple of both n and 2, you either take n itself if it's even, or multiply n by 2 if it's odd.
In C, we define a function smallestEvenMultiple that checks if n is even using the modulus operator. If n is even, the function returns n; otherwise, it multiplies n by 2 and returns the result. The main function demonstrates this by passing 5 and printing the result.
Time Complexity: O(1) since the operation involves just a modulus check and possible multiplication.
Space Complexity: O(1) as no additional space other than output is used.
Leverage the properties of bits to determine evenness. If n is even, return n; otherwise, return n << 1 which is equivalent to multiplying n by 2.
This C implementation utilizes bitwise operations to determine evenness and shift n left (equivalent to multiplication by 2) if odd.
Time Complexity: O(1)
Space Complexity: O(1)
If n is even, then the least common multiple (LCM) of 2 and n is n itself. Otherwise, the LCM of 2 and n is n times 2.
The time complexity is O(1).
| Approach | Complexity |
|---|---|
| Multiply and Check | Time Complexity: O(1) since the operation involves just a modulus check and possible multiplication. |
| Bit Manipulation | Time Complexity: O(1) |
| Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Multiply and Check (Modulo) | O(1) | O(1) | Best general solution; clear mathematical reasoning using LCM(n,2) |
| Bit Manipulation | O(1) | O(1) | When demonstrating knowledge of binary operations or avoiding modulo |
Leetcode 2413 Smallest Even Multiple | Coding Decoded SDE sheet • Coding Decoded • 1,184 views views
Watch 9 more video solutions →Practice Smallest Even Multiple with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor