Smallest Even Multiple - Solution & Explanation
Problem Statement
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 <= 150
Approach Overview
Problem 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.
Approach 1: Multiply and Check
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.
Complexity
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.
Approach 2: Bit Manipulation
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.
Complexity
Time Complexity: O(1)
Space Complexity: O(1)
Approach 3: Mathematics
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).
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 2413 Smallest Even Multiple | Coding Decoded SDE sheet • Coding Decoded • 1,190 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Smallest Even Multiple easy or hard?
Smallest Even Multiple Python/Java solution
How to solve Smallest Even Multiple in O(1)?
What is the best approach for Smallest Even Multiple?
Is Smallest Even Multiple asked at Google/Amazon/Meta?
What data structure is used in Smallest Even Multiple?
What is the time complexity of Smallest Even Multiple?
Ready to solve this problem?
Practice Smallest Even Multiple with our built-in code editor and test cases.
Practice on FleetCode