Teaching Kids Programming: Videos on Data Structures and Algorithms
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 <= 1000
1 <= arr[i] <= 1000
Algorithm of Finding Three Consecutive Odds
If the array has less than 3 numbers, we can’t definitely find three consecutive odd numbers. Starting from the third number, we can check the previous two numbers and including itself to see if it is odd.
The time complexity is O(N) but each number may be checked for odd or even multiple times – 5 times.
1 2 3 4 5 6 7 8 9 10 | class Solution: def threeConsecutiveOdds(self, arr: List[int]) -> bool: n = len(arr) if n < 3: return False isOdd = lambda x: x & 1 == 1 for i in range(2, n): if isOdd(arr[i]) and isOdd(arr[i - 1]) and isOdd(arr[i - 2]): return True return False |
class Solution: def threeConsecutiveOdds(self, arr: List[int]) -> bool: n = len(arr) if n < 3: return False isOdd = lambda x: x & 1 == 1 for i in range(2, n): if isOdd(arr[i]) and isOdd(arr[i - 1]) and isOdd(arr[i - 2]): return True return False
A better solution would be to record the count for the consecutive odd numbers so far – and then update the maximum count seen. Return true if the max count exceeds or equal to three.
1 2 3 4 5 6 7 8 9 10 11 | class Solution: def threeConsecutiveOdds(self, arr: List[int]) -> bool: maxCount = 0 cnt = 0 for i in arr: if i & 1: cnt += 1 maxCount = max(maxCount, cnt) else: cnt = 0 return maxCount >= 3 |
class Solution: def threeConsecutiveOdds(self, arr: List[int]) -> bool: maxCount = 0 cnt = 0 for i in arr: if i & 1: cnt += 1 maxCount = max(maxCount, cnt) else: cnt = 0 return maxCount >= 3
The time complexity is O(N) and space complexity is O(1) constant. Each number is checked only once for its oddity.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: A Simple PHP Function to Disable Google Fonts in WordPress
Next Post: Convert UTF Encoding to UCS in PHP