Problem of The Day: Three Consecutive Odds

Problem Statement

Intuition

My first thought when solving this problem is to iterate through the array and check if there are three consecutive odd numbers. If I find such a sequence, I return True.

Approach

I will loop through the array using an index i. For each element num at index i, I will use another index j to check the consecutive elements. I will increment j as long as the elements are odd. If the difference between j and i becomes 3, it means I have found three consecutive odd numbers, and I will return True. If the loop completes without finding such a sequence, I will return False.

Complexity

• Time complexity:

  • \(O(n)\), where n is the length of the array. In the worst case, I may need to iterate through the entire array.

• Space complexity:

  • \(O(1)\), since I am using only a few extra variables and not any additional data structures that grow with the input size.

Code

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        for i, num in enumerate(arr):
            j = i
            while j < len(arr) and arr[j] % 2:
                j += 1
            if j - i == 3:
                return True
        return False

Editorial

Approach 1: Brute Force

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        # Loop through the array up to the third-to-last element
        for i in range(len(arr) - 2):
            # Check if the current element and the next two elements are all odd
            if arr[i] % 2 == 1 and arr[i + 1] % 2 == 1 and arr[i + 2] % 2 == 1:
                return True
        return False

Approach 2: Counting

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        consecutive_odds = 0

        # Increment the counter if the number is odd,
        # else reset the counter
        for num in arr:
            # Check if the current number is odd
            if num % 2 == 1:
                consecutive_odds += 1
            else:
                consecutive_odds = 0

            # Check if there are three consecutive odd numbers
            if consecutive_odds == 3:
                return True

        return False

Approach 3: Product of Three Numbers

class Solution:
    def threeConsecutiveOdds(self, arr: list[int]) -> bool:
        # Loop through the array up to the third-to-last element
        for i in range(len(arr) - 2):
            product = arr[i] * arr[i + 1] * arr[i + 2]
            # Check if the product is odd
            if product % 2 == 1:
                return True
        return False