Teaching Kids Programming – Three Consecutive Odds


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) —

GD Star Rating
loading...
388 words
Last Post: A Simple PHP Function to Disable Google Fonts in WordPress
Next Post: Convert UTF Encoding to UCS in PHP

The Permanent URL is: Teaching Kids Programming – Three Consecutive Odds

Leave a Reply