2413. Smallest Even Multiple

EasyMathNumber Theory
Leetcode Link

Problem Description

The given problem requires determining the smallest positive integer that can be divided evenly (without leaving a remainder) by both 2 and a given positive integer n. This integer is essentially the least common multiple (LCM) of 2 and n. Since the question only involves 2 as one of the numbers, it simplifies the conditions for the LCM. If n is already an even number, then it itself is the least multiple of both 2 and n (as any even number is divisible by 2). However, if n is odd, then the smallest even multiple is simply twice the value of n, as multiplying an odd number by 2 yields the smallest even number which is a multiple of both 2 and the odd number.

Intuition

To solve this problem, we check if n is already an even number. An even number is characterized by having no remainder when divided by 2. We can check this by performing n % 2 and see if the result is 0. If n is even, then n is our answer because n would be the smallest number that is a multiple of both itself and 2.

If n is not even (implying it's odd), then the smallest even multiple that is also a multiple of n would be twice n. This is because the only way to make an odd number even (and therefore a multiple of 2) without changing its divisibility by n is to multiply it by 2.

Thus, the solution can be succinctly implemented with a single line of code that returns n if it's even, or n * 2 if it's odd.

Learn more about Math patterns.

Solution Approach

The provided solution is straightforward and does not require complicated algorithms or data structures. It leverages a straightforward mathematical fact that every multiple of an even number is even, and the smallest even multiple of an odd number is the number itself multiplied by 2.

Here is a step-by-step breakdown of the implementation process:

  1. Check if the given integer n is even by using the modulo operator %. In Python, n % 2 == 0 is True if n is divisible by 2 without any remainder. It is a common way to determine if a number is even.

  2. If n is even, the function returns n itself since n is the smallest even number that satisfies the condition of being a multiple of both n and 2.

  3. If n is odd (the check resulted in False), multiply n by 2 to find the smallest even multiple of n. Odd numbers can only yield even numbers when multiplied by an even number, and multiplying by 2 ensures the smallest possible outcome.

Please note that there is no explicit loop or conditional structures needed; the solution uses a ternary-like expression in Python that is a concise way to write an if-else statement on a single line.

The equation: return n if n % 2 == 0 else n * 2 covers the solution approach completely.

In this specific problem, the solution's time complexity is constant, O(1), because the calculation requires a maximum of two operations regardless of the size of n. The space complexity is also constant, O(1), as it does not require any additional space that depends on the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's consider an example to illustrate the solution approach. Suppose we are given n = 7, which is an odd number.

  1. First, we check if n is even by performing n % 2. For our example, 7 % 2 equals 1, which is not zero. So, n is not even.

  2. Since n is odd, our solution should return n * 2. Hence, we multiply 7 by 2, which gives us 14.

  3. The number 14 is the smallest positive integer that is even and can be divided evenly by both 2 and 7 (since the other divisor is 2, and 14 is already an even number).

Therefore, the function will return 14 as the answer in this case.

Now let's take an even number for n, for instance, n = 6.

  1. We perform the modulo operation again: 6 % 2. This time it equals 0, which means n is even.

  2. Since n is even, the smallest even multiple of 2 that can also be divided by n is n itself. There is no need to perform any multiplication.

  3. The function will return 6 as the least common multiple that meets the problem's conditions.

The key takeaway here is the simple check for evenness, which dictates whether we can return n directly or need to return n * 2. This example walkthrough demonstrates the directness and efficiency of the solution approach for both odd and even input scenarios.

Solution Implementation

1class Solution:
2    def smallestEvenMultiple(self, n: int) -> int:
3        # Check if n is even by using the modulo operator.
4        # If n is even, it is already the smallest even multiple, so we return it.
5        if n % 2 == 0:
6            return n
7        else:
8            # If n is odd, the smallest even multiple is n multiplied by 2.
9            return n * 2
10
1class Solution {
2    // Method to calculate the smallest even multiple of a given number n
3    public int smallestEvenMultiple(int n) {
4        // Check if n is already even by checking remainder when divided by 2
5        if (n % 2 == 0) {
6            // If n is even, then it is the smallest even multiple of itself
7            return n;
8        } else {
9            // If n is odd, then the smallest even multiple is n times 2
10            return n * 2;
11        }
12    }
13}
14
1class Solution {
2public:
3    // Function to find the smallest even multiple of a given number 'n'
4    int smallestEvenMultiple(int n) {
5        // If 'n' is already even, it is its own smallest even multiple
6        if (n % 2 == 0) {
7            return n;
8        }
9        // If 'n' is odd, double 'n' to get the smallest even multiple
10        return n * 2;
11    }
12};
13
1// This function finds the smallest even multiple of a given number.
2// If 'n' is already even, it returns 'n'; else it returns 'n' multiplied by 2.
3function smallestEvenMultiple(n: number): number {
4    // Check if 'n' is even using modulo operator
5    if (n % 2 === 0) {
6        // 'n' is even, so return 'n' itself
7        return n;
8    } else {
9        // 'n' is odd, so return 'n' doubled to make it even
10        return n * 2;
11    }
12}
13

Time and Space Complexity

The given code consists of a single function smallestEvenMultiple which takes an integer n and returns the smallest even multiple of n.

Time Complexity

The time complexity of this function is O(1) which means that it runs in constant time. This is because no matter the size of the input n, the function performs a maximum of one comparison (n % 2 == 0) and possibly one multiplication (n * 2). Both operations are basic arithmetic operations that take constant time to complete.

Space Complexity

The space complexity of this function is also O(1). The function uses a fixed amount of space; it allocates space for just one integer (the return value), and the amount of memory used does not scale with the input size n.

The overall performance of the code is thus highly efficient, with both time and space complexities being constant.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄