#1550

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Three Consecutive Odds

Determine if an integer array contains three consecutive odd numbers using a direct array-driven solution strategy for fast evaluation.

array

Problem Statement

Given an integer array arr, write a function to determine if the array contains at least three consecutive odd numbers. Return true if such a sequence exists and false otherwise. This problem focuses on array traversal and counting consecutive parity matches.

For example, in arr = [1,2,34,3,4,5,7,23,12], the subarray [5,7,23] consists of three consecutive odd numbers, so the function should return true. Constraints ensure 1 <= arr.length <= 1000 and 1 <= arr[i] <= 1000, emphasizing simple linear traversal for performance.

Examples

Example 1

Input: arr = [2,6,4,1]

Output: false

There are no three consecutive odds.

Example 2

Input: arr = [1,2,34,3,4,5,7,23,12]

Output: true

[5,7,23] are three consecutive odds.

Constraints

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

Solution Approach

Iterate with Consecutive Odd Counter

Traverse the array while maintaining a counter for consecutive odd numbers. Reset the counter to zero whenever an even number is encountered. Return true immediately if the counter reaches three.

Check Parity Efficiently

Use modulo operations to determine if each number is odd. This array-driven parity check ensures minimal computation per element and avoids nested loops, keeping the time complexity linear.

Early Termination on Success

Stop iteration as soon as three consecutive odds are found. This prevents unnecessary checks in longer arrays and aligns with the problem's failure mode, where missing early detection would lead to extra iterations.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because each element is checked once for parity. Space complexity is O(1) since only a single counter variable is maintained regardless of array size.

What Interviewers Usually Probe

Look for early return opportunities when consecutive odd count reaches three.
Emphasize a simple linear scan instead of nested loops or extra arrays.
Expect you to handle all edge cases, like arrays shorter than three elements.

Common Pitfalls or Variants

Common pitfalls

Resetting the consecutive odd counter incorrectly when encountering even numbers.
Using additional arrays unnecessarily instead of a single counter.
Failing to account for arrays with exactly three elements or fewer.

Follow-up variants

Check for k consecutive odd numbers instead of exactly three, adjusting the counter threshold.
Detect three consecutive even numbers using the same array-driven parity strategy.
Count the number of segments with three consecutive odds instead of just returning a boolean.

FAQ

What is the simplest approach for Three Consecutive Odds?

Iterate through the array with a counter for consecutive odd numbers, resetting the counter on even numbers, and return true if the counter reaches three.

Can this be solved without extra space?

Yes, maintaining a single integer counter suffices, keeping the space complexity O(1).

What if the array has fewer than three elements?

Return false immediately since it's impossible to have three consecutive odd numbers in fewer than three elements.

How does early termination help in this problem?

Stopping iteration once three consecutive odds are found prevents unnecessary checks, improving efficiency for larger arrays.

Does GhostInterview suggest checking parity explicitly?

Yes, it reinforces using modulo operations to identify odd numbers, aligning with the array-driven solution strategy.

terminal

Solution

Solution 1: Iteration + Counting

We use a variable $\textit{cnt}$ to record the current count of consecutive odd numbers.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        cnt = 0
        for x in arr:
            if x & 1:
                cnt += 1
                if cnt == 3:
                    return True
            else:
                cnt = 0
        return False

Solution 2: Iteration + Bitwise Operation

Based on the properties of bitwise operations, the result of a bitwise AND operation between two numbers is odd if and only if both numbers are odd. If there are three consecutive numbers whose bitwise AND result is odd, then these three numbers are all odd.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        cnt = 0
        for x in arr:
            if x & 1:
                cnt += 1
                if cnt == 3:
                    return True
            else:
                cnt = 0
        return False

Continue Practicing

#1552 magnetic force between two balls #1547 minimum cost to cut a stick #1546 maximum number of non overlapping subarrays with sum equals target