LeetCode 2413 - Smallest Even Multiple

LeetCode Problem 2413

Difficulty: 🟢 Easy
Topics: Math, Number Theory

Solution

Problem Understanding

The problem asks us to find the smallest positive integer that is a multiple of both 2 and a given positive integer n. In other words, we are looking for the least common multiple (LCM) of 2 and n. The input n is guaranteed to be between 1 and 150, which is a very small range. This allows for straightforward arithmetic without worrying about integer overflow.

The key observation is that 2 is very small, and any number that is even is automatically a multiple of 2. If n is already even, the smallest multiple of both 2 and n is just n. If n is odd, multiplying it by 2 produces the smallest even number divisible by n. Edge cases to consider include n = 1 (smallest possible input), and n = 2 (already even).

Approaches

The brute-force approach would be to start at n and increment by 1 until we find a number divisible by both 2 and n. While this works, it is inefficient, especially for larger numbers. Given the constraints, this is not critical, but it is unnecessary.

The optimal approach leverages the observation about parity: if n is even, return n; if n is odd, return 2 * n. This works because multiplying an odd number by 2 guarantees it is divisible by both n and 2. There is no need for loops or additional data structures.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Increment from n until a number divisible by 2 and n is found
Optimal	O(1)	O(1)	Check if n is even; if not, return 2 * n

Algorithm Walkthrough

1. Check if the input number n is even. This can be done using the modulo operator: n % 2 == 0.
2. If n is even, it is already divisible by 2 and itself, so return n.
3. If n is odd, multiply n by 2 to ensure the result is divisible by both 2 and n.
4. Return the resulting number.

Why it works: This works because every even number is divisible by 2. If n is odd, 2 * n is the smallest even multiple of n because multiplying by 2 preserves divisibility by n while ensuring it is even. The algorithm guarantees correctness with only a single conditional check.

Python Solution

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

The Python implementation follows the algorithm exactly. The modulo operator checks whether n is even. If it is, we return n. If not, we double it. This ensures minimal computation and direct handling of all inputs within the constraints.

Go Solution

func smallestEvenMultiple(n int) int {
    if n%2 == 0 {
        return n
    }
    return 2 * n
}

The Go implementation mirrors the Python logic. The % operator checks parity, and the conditional returns either n or 2 * n. There are no special considerations for overflow or slices, since the input range is small and Go integers can handle the maximum product 2 * 150 safely.

Worked Examples

Example 1: n = 5

Since 5 is odd, multiply by 2. Result is 10.

Step	n	Condition	Result
1	5	5 % 2 != 0	2 * 5 = 10
2	10	Return	10

Example 2: n = 6

Since 6 is even, return 6.

Step	n	Condition	Result
1	6	6 % 2 == 0	Return 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a single modulo and possible multiplication are performed
Space	O(1)	No extra space is used, only primitive variables

The complexity is minimal because the algorithm involves a single arithmetic check and conditional, independent of the value of n.

Test Cases

# Provided examples
assert Solution().smallestEvenMultiple(5) == 10  # odd n
assert Solution().smallestEvenMultiple(6) == 6   # even n

# Boundary cases
assert Solution().smallestEvenMultiple(1) == 2   # smallest n
assert Solution().smallestEvenMultiple(2) == 2   # smallest even n
assert Solution().smallestEvenMultiple(150) == 150  # largest even n
assert Solution().smallestEvenMultiple(149) == 298  # largest odd n

# Random cases
assert Solution().smallestEvenMultiple(3) == 6
assert Solution().smallestEvenMultiple(7) == 14
assert Solution().smallestEvenMultiple(10) == 10

Test	Why
5	Odd number multiplies by 2
6	Even number returns itself
1	Edge case of smallest n
2	Smallest even n
150	Largest even n
149	Largest odd n
3, 7, 10	Random test coverage

Edge Cases

First, n = 1 is the smallest positive integer. Multiplying by 2 is necessary since 1 is odd, ensuring the returned value is even. Second, n = 2 is already even. Returning n directly is correct because it is divisible by both 2 and itself. Third, the largest input n = 150 tests that no arithmetic overflow occurs. Since 2 * 150 = 300 is well within standard integer ranges, the implementation handles it without issues. All other odd and even numbers between 1 and 150 are handled uniformly by the simple conditional.