Problem Informations

• Problem Index: 1550
• Problem Link: Three Consecutive Odds
• Topics: Array

Problem Description

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 \leq arr.length \leq 1000$
• $1 \leq arr[i] \leq 1000$

Intuition

The problem is a straightforward condition check that asks for the presence of three consecutive odd numbers in an integer array. This requirement suggests the need for a simple traversal of the array to count consecutive odd numbers. If, during the traversal, we encounter three odd numbers in a row, we immediately confirm their existence and return true; otherwise, if the loop completes without such a pattern, we return false.

Approach

To solve this problem, we iterate over the array from end to start, maintaining a counter, oddCount, to track the number of consecutive odd numbers encountered. We employ the following approach:

1. Initialize a counter oddCount to zero. This counter will help in tracking the consecutive odd numbers.
2. Begin iterating the array from the end to the start. For each element arr[i], determine its parity:
   • If arr[i] is an odd number, indicated by the condition arr[i] & 1 (the result of a bitwise AND operation between arr[i] and 1, which will be true for odd numbers), increment oddCount by one.
   • If arr[i] is even, reset oddCount to zero as the consecutive odd sequence is broken.
3. During this iteration, if at any point oddCount reaches three, it means we have encountered three consecutive odd numbers, and we can immediately return true.
4. If the loop completes and we have never reached three consecutive odd numbers, return false.

This approach efficiently utilizes the properties of bitwise operations to determine the oddness of a number and ensures optimal performance with a linear scan of the input array, making it suitable for the given constraint of up to 1000 elements.

Code

C++

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        int oddCount = 0; // Initialize a counter for consecutive odd numbers

        // Traverse the array from the end to the beginning
        for (int i = arr.size() - 1; i >= 0; i--) {
            // Check if the current number is odd using a bitwise AND operation
            if (arr[i] & 1) {
                oddCount++; // Increment the odd number counter
                if (oddCount >= 3) {
                    return true; // Return true if there are three consecutive odd numbers
                }
            } else {
                oddCount = 0; // Reset the counter if an even number is encountered
            }
        }
        
        return false; // Return false if no three consecutive odd numbers are found
    }
};

Python

class Solution:
    def threeConsecutiveOdds(self, arr):
        oddCount = 0  # Initialize a counter for consecutive odd numbers

        # Traverse the array from the end to the beginning
        for i in range(len(arr) - 1, -1, -1):
            # Check if the current number is odd using a bitwise AND operation
            if arr[i] & 1:
                oddCount += 1  # Increment the odd number counter
                if oddCount >= 3:
                    return True  # Return true if there are three consecutive odd numbers
            else:
                oddCount = 0  # Reset the counter if an even number is encountered

        return False  # Return false if no three consecutive odd numbers are found

Complexity

• Time complexity: $O(n)$ because the algorithm traverses the array once, where $n$ is the size of the array.
• Space complexity: $O(1)$ because the algorithm uses a constant amount of additional space regardless of the input size, specifically for storing the counter oddCount.