1550. Three Consecutive Odds
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 64.5%
Problem Breakdown
The problem asks us to determine if there are three consecutive odd numbers in a given integer array arr. The input is an array of integers, and the output should be a boolean value: true if there are three consecutive odd numbers, otherwise false.
Inputs:
- An integer array
arrwith length between 1 and 1000. - Each element in the array is an integer between 1 and 1000.
Outputs:
- A boolean value (
trueorfalse).
Implicit Constraints/Edge Cases:
- The array could be very short (length 1 or 2), in which case it’s impossible to have three consecutive odd numbers.
- All elements are positive integers, so we don’t need to handle negative numbers or zero.
Intuition
A brute-force approach would involve checking every possible triplet of consecutive numbers in the array. This would work but is inefficient with a time complexity of O(n^2), where n is the length of the array.
The key insight is that we can solve this problem in a single pass through the array (O(n) time complexity) by keeping track of how many consecutive odd numbers we’ve seen so far. If at any point we have three consecutive odd numbers, we can immediately return true. Otherwise, if we finish iterating through the array without finding such a triplet, we return false.
Approach
- Initialize a counter variable
consecutive_oddsto 0. - Iterate through each element in the array:
- If the current element is odd (i.e.,
arr[i] % 2 != 0), increment theconsecutive_oddscounter. - If the
consecutive_oddscounter reaches 3, returntrue. - If the current element is even, reset the
consecutive_oddscounter to 0.
- If the current element is odd (i.e.,
- After iterating through the array, if we haven’t found three consecutive odd numbers, return
false.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. We make a single pass through the array.
- Space Complexity: O(1). We use only a constant amount of extra space for the counter variable.
Solution
def threeConsecutiveOdds(arr):
consecutive_odds = 0
for num in arr:
if num % 2 != 0: # Check if the number is odd
consecutive_odds += 1
if consecutive_odds == 3:
return True
else:
consecutive_odds = 0
return False
Edge Cases Handled
- Short arrays (length 1 or 2): The function will correctly return
falsesince it’s impossible to have three consecutive odd numbers in such cases. - All even numbers: The counter will never reach 3, so the function will return
false. - Array with only one odd number followed by two even numbers: The counter will reset after encountering the single odd number, ensuring correct behavior.