Problem Description

You are given an integer array arr. Your task is to determine whether the array contains three consecutive odd numbers.

The problem asks you to check if there exists any position in the array where three odd numbers appear one after another. If such a sequence exists, return true. Otherwise, return false.

For example:

• If arr = [2, 6, 4, 1], the answer would be false because there are no three consecutive odd numbers
• If arr = [1, 2, 34, 3, 4, 5, 7, 23, 12], the answer would be true because the numbers 5, 7, 23 at indices 5, 6, and 7 are three consecutive odd numbers

The solution uses a counter approach where it tracks how many consecutive odd numbers have been encountered. When iterating through the array:

• If the current number is odd (checked using x & 1), increment the counter
• If the counter reaches 3, we've found three consecutive odd numbers
• If the current number is even, reset the counter to 0 since the consecutive sequence is broken

Intuition

The key insight is that we need to track consecutive odd numbers as we traverse the array. Think of it like keeping a running streak - every time we encounter an odd number, our streak continues and grows. But the moment we hit an even number, the streak breaks and we must start counting from zero again.

Why does this work? Because "consecutive" means the odd numbers must appear right next to each other in the array. If there's even a single even number between them, they're no longer consecutive.

We can check if a number is odd using the bitwise AND operation x & 1. This works because odd numbers always have their least significant bit set to 1 in binary representation, while even numbers have it set to 0. So x & 1 returns 1 for odd numbers and 0 for even numbers.

The counting approach emerges naturally from this observation:

• Start with a counter at 0
• Each odd number increments our counter (building the streak)
• Each even number resets our counter to 0 (breaking the streak)
• As soon as our counter reaches 3, we know we've found three consecutive odd numbers

This gives us a single-pass solution with O(n) time complexity and O(1) space complexity, as we only need to maintain one counter variable while iterating through the array once.

Solution Approach

We implement the solution using iteration and counting. The approach uses a single variable cnt to track the current count of consecutive odd numbers as we traverse through the array.

Here's how the implementation works step by step:

1. Initialize the counter: Start with cnt = 0 to track consecutive odd numbers.

2. Iterate through the array: Process each element x in the array one by one.

3. Check if the current number is odd: Use the bitwise AND operation x & 1:

   • If x & 1 evaluates to 1 (truthy), the number is odd
   • If x & 1 evaluates to 0 (falsy), the number is even

4. Update the counter based on parity:

   • If odd: Increment cnt by 1 (cnt += 1)
     • After incrementing, check if cnt == 3
     • If yes, we've found three consecutive odd numbers, so return True
   • If even: Reset cnt to 0 since the consecutive sequence is broken

5. Final check: If we complete the iteration without finding three consecutive odd numbers, return False.

The algorithm processes each element exactly once, making it efficient with O(n) time complexity where n is the length of the array. The space complexity is O(1) since we only use a single counter variable regardless of the input size.

This pattern of maintaining a counter that resets on certain conditions is common in problems involving consecutive elements or streaks in arrays.

Example Walkthrough

Let's trace through the algorithm with the array arr = [1, 2, 34, 3, 4, 5, 7, 23, 12].

We'll track our counter cnt as we process each element:

Initial state: cnt = 0

Step 1: Process arr[0] = 1

• Check: 1 & 1 = 1 (odd number)
• Action: Increment cnt to 1
• Check if cnt == 3? No, continue

Step 2: Process arr[1] = 2

• Check: 2 & 1 = 0 (even number)
• Action: Reset cnt to 0

Step 3: Process arr[2] = 34

• Check: 34 & 1 = 0 (even number)
• Action: Reset cnt to 0 (already 0)

Step 4: Process arr[3] = 3

• Check: 3 & 1 = 1 (odd number)
• Action: Increment cnt to 1
• Check if cnt == 3? No, continue

Step 5: Process arr[4] = 4

• Check: 4 & 1 = 0 (even number)
• Action: Reset cnt to 0

Step 6: Process arr[5] = 5

• Check: 5 & 1 = 1 (odd number)
• Action: Increment cnt to 1
• Check if cnt == 3? No, continue

Step 7: Process arr[6] = 7

• Check: 7 & 1 = 1 (odd number)
• Action: Increment cnt to 2
• Check if cnt == 3? No, continue

Step 8: Process arr[7] = 23

• Check: 23 & 1 = 1 (odd number)
• Action: Increment cnt to 3
• Check if cnt == 3? Yes! Return True

We found three consecutive odd numbers (5, 7, 23) at indices 5, 6, and 7, so the function returns True.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array arr. The algorithm iterates through the array exactly once, checking each element to determine if it's odd (using the bitwise AND operation x & 1) and maintaining a counter. Each operation within the loop takes constant time O(1), so the overall time complexity is linear with respect to the input size.

The space complexity is O(1). The algorithm only uses a single integer variable cnt to keep track of consecutive odd numbers, regardless of the input array size. No additional data structures are created that scale with the input, making the space usage constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly checking for odd numbers

A common mistake is using the wrong condition to check if a number is odd. Some developers might write:

• if number % 2 == 1 - This fails for negative odd numbers (e.g., -3 % 2 returns -1 in Python, not 1)
• if number / 2 != number // 2 - This uses floating-point division which can be inefficient

Solution: Use either number & 1 (bitwise AND) or number % 2 != 0 which work correctly for both positive and negative numbers.

2. Not resetting the counter properly

Developers might forget to reset the counter when encountering an even number, leading to incorrect counting of non-consecutive odd numbers:

# Incorrect - counts any three odd numbers, not consecutive ones
count = 0
for num in arr:
    if num & 1:
        count += 1
    if count == 3:
        return True
return False

Solution: Always reset the counter to 0 when an even number is encountered to ensure we're only counting consecutive odd numbers.

3. Off-by-one errors in counter logic

Some might check for the wrong count value or increment at the wrong time:

# Incorrect - returns True after finding only 2 consecutive odds
if consecutive_odd_count >= 2:
    return True

Solution: Ensure the counter is checked against exactly 3, and the check happens after incrementing.

4. Using sliding window when not needed

Overcomplicating with a sliding window approach:

# Unnecessarily complex
for i in range(len(arr) - 2):
    if arr[i] & 1 and arr[i+1] & 1 and arr[i+2] & 1:
        return True

While this works, it requires boundary checking and is less elegant.

Solution: The simple counter approach is cleaner and handles all edge cases naturally without explicit boundary checks.