2413. Smallest Even Multiple
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:
-
Check if the given integer
n
is even by using the modulo operator%
. In Python,n % 2 == 0
isTrue
ifn
is divisible by2
without any remainder. It is a common way to determine if a number is even. -
If
n
is even, the function returnsn
itself sincen
is the smallest even number that satisfies the condition of being a multiple of bothn
and2
. -
If
n
is odd (the check resulted inFalse
), multiplyn
by2
to find the smallest even multiple ofn
. Odd numbers can only yield even numbers when multiplied by an even number, and multiplying by2
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example to illustrate the solution approach. Suppose we are given n = 7
, which is an odd number.
-
First, we check if
n
is even by performingn % 2
. For our example,7 % 2
equals1
, which is not zero. So,n
is not even. -
Since
n
is odd, our solution should returnn * 2
. Hence, we multiply7
by2
, which gives us14
. -
The number
14
is the smallest positive integer that is even and can be divided evenly by both2
and7
(since the other divisor is2
, and14
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
.
-
We perform the modulo operation again:
6 % 2
. This time it equals0
, which meansn
is even. -
Since
n
is even, the smallest even multiple of2
that can also be divided byn
isn
itself. There is no need to perform any multiplication. -
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.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!