Jobs

Interviews

Discussions

Three Consecutive Odds

Easy

Asked by:

24 views

Topics:

Arrays

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

Try coding it in LeetCode

Three Consecutive Odds

Easy

Asked by:

24 views

Topics:

Arrays

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

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 integer values within the input array?
Can the input array be empty or contain fewer than three elements?
Is the expected return value a boolean indicating the existence of three consecutive odds, or something else?
Does the definition of 'odd' refer to integers not divisible by two, or are there other considerations?
If there are multiple sets of three consecutive odd numbers, should I return `true` after finding the first one?

Brute Force Solution

Approach

The brute-force method for this problem is to examine every possible set of three consecutive numbers. We check each group to see if they are all odd. If we find such a group, we are done.

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

Start by looking at the first three numbers in the list.
Check if all three of these numbers are odd.
If they are, we have found our answer and can stop.
If not, move to the next group of three numbers: the second, third, and fourth numbers.
Check if all three of these numbers are odd.
Repeat this process, moving one number at a time, until you reach the end of the list or find a group of three odd numbers in a row.
If you reach the end of the list without finding any three consecutive odd numbers, then the answer is no.

Code Implementation

def three_consecutive_odds(numbers):
    list_length = len(numbers)

    # Iterate through the list, checking sets of three numbers.
    for index in range(list_length - 2):
        # Check if the current three numbers are all odd.
        if (numbers[index] % 2 != 0 and
            numbers[index + 1] % 2 != 0 and
            numbers[index + 2] % 2 != 0):

            # If all three are odd, return True.
            return True

    # If the loop finishes without finding three consecutive odds, return False.
    return False

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array `nums` of size `n`. In each iteration, it checks a fixed-size window of three consecutive numbers to see if they are all odd. The number of these checks depends linearly on `n` because, in the worst-case scenario, the algorithm needs to slide this window across nearly the entire array to find the three odds or determine that they don't exist. Therefore, the time complexity is directly proportional to the input size `n`, leading to O(n).

Space Complexity

O(1) – The provided algorithm iterates through the input array `nums` checking groups of three consecutive numbers. It does not use any auxiliary data structures like lists, hash maps, or recursion. The algorithm only uses a constant number of variables (for indexing and potentially a boolean flag) regardless of the input array's size (N, where N is the length of the `nums` array). Therefore, the space complexity is constant.

Optimal Solution

Approach

The problem asks us to check if a list of numbers contains three odd numbers in a row. The most efficient approach is to simply go through the list once, checking each group of three consecutive numbers to see if they are all odd. As soon as we find such a group, we can stop and declare success.

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

Start at the beginning of the list of numbers.
Look at the first three numbers in a row.
Check if all three of those numbers are odd.
If they are all odd, we're done! The answer is yes.
If they are not all odd, move on to the next group of three numbers (starting with the second number in the original list).
Keep doing this until you find three odd numbers in a row, or until you reach the end of the list.
If you reach the end of the list without finding three odd numbers in a row, the answer is no.

Code Implementation

def three_consecutive_odds(numbers):
    for i in range(len(numbers) - 2): 
        # Iterate up to the point where 3 consecutive numbers can be checked.

        if (numbers[i] % 2 != 0 and \
            numbers[i+1] % 2 != 0 and \
            numbers[i+2] % 2 != 0): 
            # Check if the current group of three are all odd.

            return True # Return immediately if a match is found.

    return False # No three consecutive odd numbers found.

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of numbers once. In each iteration, it checks if the current group of three consecutive numbers are all odd. The number of iterations is directly proportional to the length of the input list, n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm iterates through the input list, checking groups of three consecutive numbers. It does not create any auxiliary data structures like lists, maps, or sets to store information. The space used consists only of a fixed number of variables (for example, an index or counter), which is independent of the input list's size (N). Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return false, depending on language conventions.
Input array with fewer than 3 elements	Return false, as three consecutive odd numbers are impossible.
Input array with all even numbers	Return false as no three consecutive odd numbers are present.
Input array with very large numbers that could cause overflow during calculations (if applicable)	Use appropriate data types (e.g., long) to prevent integer overflow, or consider using a boolean check for oddness rather than mathematical operations.
Input array with negative odd numbers	The solution should correctly identify negative odd numbers; the parity check should handle negative odd numbers correctly.
Input array containing zero	Zero is even and should be handled correctly in the odd number check.
Array with alternating odd and even numbers	The solution will correctly identify that there are no three consecutive odd numbers.
Very large input array to test performance.	The solution should iterate through the array only once, providing O(n) time complexity.

Null input array

How to Handle:

Throw an IllegalArgumentException or return false, depending on language conventions.

Input array with fewer than 3 elements

How to Handle:

Return false, as three consecutive odd numbers are impossible.

Input array with all even numbers

How to Handle:

Return false as no three consecutive odd numbers are present.

Input array with very large numbers that could cause overflow during calculations (if applicable)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow, or consider using a boolean check for oddness rather than mathematical operations.

Input array with negative odd numbers

How to Handle:

The solution should correctly identify negative odd numbers; the parity check should handle negative odd numbers correctly.

Input array containing zero

How to Handle:

Zero is even and should be handled correctly in the odd number check.

Array with alternating odd and even numbers

How to Handle:

The solution will correctly identify that there are no three consecutive odd numbers.

Very large input array to test performance.

How to Handle:

The solution should iterate through the array only once, providing O(n) time complexity.

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 integer values within the input array?
Can the input array be empty or contain fewer than three elements?
Is the expected return value a boolean indicating the existence of three consecutive odds, or something else?
Does the definition of 'odd' refer to integers not divisible by two, or are there other considerations?
If there are multiple sets of three consecutive odd numbers, should I return `true` after finding the first one?

Brute Force Solution

Approach

The brute-force method for this problem is to examine every possible set of three consecutive numbers. We check each group to see if they are all odd. If we find such a group, we are done.

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

Start by looking at the first three numbers in the list.
Check if all three of these numbers are odd.
If they are, we have found our answer and can stop.
If not, move to the next group of three numbers: the second, third, and fourth numbers.
Check if all three of these numbers are odd.
Repeat this process, moving one number at a time, until you reach the end of the list or find a group of three odd numbers in a row.
If you reach the end of the list without finding any three consecutive odd numbers, then the answer is no.

Code Implementation

def three_consecutive_odds(numbers):
    list_length = len(numbers)

    # Iterate through the list, checking sets of three numbers.
    for index in range(list_length - 2):
        # Check if the current three numbers are all odd.
        if (numbers[index] % 2 != 0 and
            numbers[index + 1] % 2 != 0 and
            numbers[index + 2] % 2 != 0):

            # If all three are odd, return True.
            return True

    # If the loop finishes without finding three consecutive odds, return False.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the beginning of the list of numbers.
Look at the first three numbers in a row.
Check if all three of those numbers are odd.
If they are all odd, we're done! The answer is yes.
If they are not all odd, move on to the next group of three numbers (starting with the second number in the original list).
Keep doing this until you find three odd numbers in a row, or until you reach the end of the list.
If you reach the end of the list without finding three odd numbers in a row, the answer is no.

Code Implementation

def three_consecutive_odds(numbers):
    for i in range(len(numbers) - 2): 
        # Iterate up to the point where 3 consecutive numbers can be checked.

        if (numbers[i] % 2 != 0 and \
            numbers[i+1] % 2 != 0 and \
            numbers[i+2] % 2 != 0): 
            # Check if the current group of three are all odd.

            return True # Return immediately if a match is found.

    return False # No three consecutive odd numbers found.

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return false, depending on language conventions.
Input array with fewer than 3 elements	Return false, as three consecutive odd numbers are impossible.
Input array with all even numbers	Return false as no three consecutive odd numbers are present.
Input array with very large numbers that could cause overflow during calculations (if applicable)	Use appropriate data types (e.g., long) to prevent integer overflow, or consider using a boolean check for oddness rather than mathematical operations.
Input array with negative odd numbers	The solution should correctly identify negative odd numbers; the parity check should handle negative odd numbers correctly.
Input array containing zero	Zero is even and should be handled correctly in the odd number check.
Array with alternating odd and even numbers	The solution will correctly identify that there are no three consecutive odd numbers.
Very large input array to test performance.	The solution should iterate through the array only once, providing O(n) time complexity.

Null input array

How to Handle:

Throw an IllegalArgumentException or return false, depending on language conventions.

Input array with fewer than 3 elements

How to Handle:

Return false, as three consecutive odd numbers are impossible.

Input array with all even numbers

How to Handle:

Return false as no three consecutive odd numbers are present.

Input array with very large numbers that could cause overflow during calculations (if applicable)

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow, or consider using a boolean check for oddness rather than mathematical operations.

Input array with negative odd numbers

How to Handle:

The solution should correctly identify negative odd numbers; the parity check should handle negative odd numbers correctly.

Input array containing zero

How to Handle:

Zero is even and should be handled correctly in the odd number check.

Array with alternating odd and even numbers

How to Handle:

The solution will correctly identify that there are no three consecutive odd numbers.

Very large input array to test performance.

How to Handle:

The solution should iterate through the array only once, providing O(n) time complexity.