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 <= arr.length <= 10001 <= arr[i] <= 1000
Solutions
Solution 1: Iteration + Counting
We use a variable cnt to record the current count of consecutive odd numbers.
Next, we iterate through the array. If the current element is odd, then cnt is incremented by one. If cnt equals 3, then return True. If the current element is even, then cnt is reset to zero.
After the iteration, if three consecutive odd numbers are not found, then return False.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
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(code-box)
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.
Therefore, we only need to iterate through the array and check if there exists three consecutive numbers whose bitwise AND result is odd. If such numbers exist, return True; otherwise, return False.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
class Solution: def threeConsecutiveOdds(self, arr: List[int]) -> bool: return any(x & arr[i + 1] & arr[i + 2] & 1 for i, x in enumerate(arr[:-2]))(code-box)
