Jobs

Interviews

Discussions

Smallest Even Multiple

Easy

Asked by:

More companies

101 views

Topics:

Greedy AlgorithmsBit Manipulation

Given a positive integer 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

Try coding it in LeetCode

Smallest Even Multiple

Easy

Asked by:

101 views

Topics:

Greedy AlgorithmsBit Manipulation

Given a positive integer 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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer n?
Is n guaranteed to be a positive integer, or could it be zero or negative?
If n is even, should I simply return n?
Are there any specific performance considerations or constraints for very large values of n?
Are we optimizing for space complexity or is time complexity the only concern?

Brute Force Solution

Approach

The brute force method for this problem involves checking multiples of the given number one by one. We will keep testing these multiples until we find one that is also an even number. That even multiple will be our answer.

Here's how the algorithm would work step-by-step:

Start with the number itself.
Check if that number is divisible by 2 (meaning it's an even number).
If it is even, you've found the answer!
If the number is not even, move to the next multiple, which is the number times 2.
Check if this new multiple is divisible by 2.
If it is, then you've found the answer!
If it is not, continue to keep incrementing your multiple (number times 3, number times 4, and so on), checking if each one is an even number, until you find one.

Code Implementation

def smallest_even_multiple_brute_force(given_number):
    multiple_count = 1

    while True:
        current_multiple = given_number * multiple_count

        # Check if the current multiple is even.
        if current_multiple % 2 == 0:

            # If the multiple is even, we've found our answer.
            return current_multiple

        # Increment to the next multiple.
        multiple_count += 1

Big(O) Analysis

Time Complexity

O(1) – The algorithm checks multiples of the input number `n` until an even multiple is found. Since the first multiple checked is `n` itself, and the second multiple is `2n`, one of these will always be even. Thus, at most two checks are performed, regardless of the value of `n`. Therefore, the number of operations is constant. This constant number of operations is O(1).

Space Complexity

O(1) – The provided solution only uses a few integer variables: the input number itself, and a temporary variable to hold the multiple being checked. The number of variables remains constant regardless of the input number. Therefore, the space complexity is constant, or O(1).

Optimal Solution

Approach

The goal is to find the smallest number that is both a multiple of a given number and is also an even number. The simplest approach uses the properties of even numbers and multiples to avoid unnecessary calculations.

Here's how the algorithm would work step-by-step:

Check if the given number is already even.
If the number is even, then it is already a multiple of itself and even, so it is the answer.
If the number is odd, then multiply it by 2. Multiplying any odd number by 2 always results in an even number, and it is guaranteed to be the smallest even multiple.

Code Implementation

def smallest_even_multiple(given_number):
    # Check if the number is even
    if given_number % 2 == 0:
        # If even, it's already the smallest even multiple
        return given_number

    # If the number is odd
    else:
        # Multiply by 2 to get the smallest even multiple
        smallest_even_multiple_result = given_number * 2
        return smallest_even_multiple_result

Big(O) Analysis

Time Complexity

O(1) – The solution involves a simple conditional check to determine if the input number is even. If it is, the number itself is returned; otherwise, the number is multiplied by 2. Both the conditional check and the multiplication are constant-time operations, independent of the input number's size. Therefore, the time complexity remains constant, regardless of the input.

Space Complexity

O(1) – The algorithm only uses a single integer variable to store the input number and potentially another to store the result of the multiplication (if the input is odd). No additional data structures or collections are created. Therefore, the space used is constant and does not depend on the size of the input number N. The space complexity is O(1).

Edge Cases

Case	How to Handle
n is 1	Return 2 immediately as 2 is the smallest multiple of 2 and 1.
n is already even	Return n itself, as it's already a multiple of 2.
n is a large odd number close to the maximum integer limit	Multiply n by 2, which may require checking for integer overflow.
n is 0	Define the expected behavior: either throw an error or return 0 by definition, because any number is a multiple of 0 and 2, the smallest could be 0.
n is a negative number	Handle invalid input by either throwing an exception or taking the absolute value of n to process the positive counterpart.
n is the maximum integer value	Multiplying by 2 leads to integer overflow; return an error or use a larger integer type.
n is a floating-point number	Reject floating-point numbers, requiring the input to be an integer to maintain mathematical correctness.
Null or undefined input	Throw an IllegalArgumentException or return a predefined error value to indicate invalid input.

n is 1

How to Handle:

Return 2 immediately as 2 is the smallest multiple of 2 and 1.

n is already even

How to Handle:

Return n itself, as it's already a multiple of 2.

n is a large odd number close to the maximum integer limit

How to Handle:

Multiply n by 2, which may require checking for integer overflow.

n is 0

How to Handle:

Define the expected behavior: either throw an error or return 0 by definition, because any number is a multiple of 0 and 2, the smallest could be 0.

n is a negative number

How to Handle:

Handle invalid input by either throwing an exception or taking the absolute value of n to process the positive counterpart.

n is the maximum integer value

How to Handle:

Multiplying by 2 leads to integer overflow; return an error or use a larger integer type.

n is a floating-point number

How to Handle:

Reject floating-point numbers, requiring the input to be an integer to maintain mathematical correctness.

Null or undefined input

How to Handle:

Throw an IllegalArgumentException or return a predefined error value to indicate invalid input.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer n?
Is n guaranteed to be a positive integer, or could it be zero or negative?
If n is even, should I simply return n?
Are there any specific performance considerations or constraints for very large values of n?
Are we optimizing for space complexity or is time complexity the only concern?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number itself.
Check if that number is divisible by 2 (meaning it's an even number).
If it is even, you've found the answer!
If the number is not even, move to the next multiple, which is the number times 2.
Check if this new multiple is divisible by 2.
If it is, then you've found the answer!
If it is not, continue to keep incrementing your multiple (number times 3, number times 4, and so on), checking if each one is an even number, until you find one.

Code Implementation

def smallest_even_multiple_brute_force(given_number):
    multiple_count = 1

    while True:
        current_multiple = given_number * multiple_count

        # Check if the current multiple is even.
        if current_multiple % 2 == 0:

            # If the multiple is even, we've found our answer.
            return current_multiple

        # Increment to the next multiple.
        multiple_count += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Check if the given number is already even.
If the number is even, then it is already a multiple of itself and even, so it is the answer.
If the number is odd, then multiply it by 2. Multiplying any odd number by 2 always results in an even number, and it is guaranteed to be the smallest even multiple.

Code Implementation

def smallest_even_multiple(given_number):
    # Check if the number is even
    if given_number % 2 == 0:
        # If even, it's already the smallest even multiple
        return given_number

    # If the number is odd
    else:
        # Multiply by 2 to get the smallest even multiple
        smallest_even_multiple_result = given_number * 2
        return smallest_even_multiple_result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 1	Return 2 immediately as 2 is the smallest multiple of 2 and 1.
n is already even	Return n itself, as it's already a multiple of 2.
n is a large odd number close to the maximum integer limit	Multiply n by 2, which may require checking for integer overflow.
n is 0	Define the expected behavior: either throw an error or return 0 by definition, because any number is a multiple of 0 and 2, the smallest could be 0.
n is a negative number	Handle invalid input by either throwing an exception or taking the absolute value of n to process the positive counterpart.
n is the maximum integer value	Multiplying by 2 leads to integer overflow; return an error or use a larger integer type.
n is a floating-point number	Reject floating-point numbers, requiring the input to be an integer to maintain mathematical correctness.
Null or undefined input	Throw an IllegalArgumentException or return a predefined error value to indicate invalid input.

n is 1

How to Handle:

Return 2 immediately as 2 is the smallest multiple of 2 and 1.

n is already even

How to Handle:

Return n itself, as it's already a multiple of 2.

n is a large odd number close to the maximum integer limit

How to Handle:

Multiply n by 2, which may require checking for integer overflow.

n is 0

How to Handle:

Define the expected behavior: either throw an error or return 0 by definition, because any number is a multiple of 0 and 2, the smallest could be 0.

n is a negative number

How to Handle:

Handle invalid input by either throwing an exception or taking the absolute value of n to process the positive counterpart.

n is the maximum integer value

How to Handle:

Multiplying by 2 leads to integer overflow; return an error or use a larger integer type.

n is a floating-point number

How to Handle:

Reject floating-point numbers, requiring the input to be an integer to maintain mathematical correctness.

Null or undefined input

How to Handle:

Throw an IllegalArgumentException or return a predefined error value to indicate invalid input.