Problem Description

In this problem, we are given an array of integers, named arr. Our objective is to determine whether the array contains a sequence of three consecutive odd numbers. If such a sequence exists, we should return true; if not, we should return false.

To be classified as odd, a number must have a remainder of 1 when divided by 2. A sequence of three consecutive odd numbers is a subsequence in the array where each of the three numbers appears one after another and each is odd.

Intuition

To solve this problem, we scan through the array, starting from the first element and continuing until the third-to-last element (because we are checking sequences of three). For each element i, we need to check that element i, i+1 (the next element), and i+2 (the element after the next) are all odd.

The simplest way to do this is to check the remainder when each number is divided by 2. This is achieved using the modulo operator %. If a number is odd, number % 2 will equal 1, and if the number is even, it will equal 0. By summing up the remainders of the current element and the next two (arr[i] % 2 + arr[i + 1] % 2 + arr[i + 2] % 2), we can quickly verify if all three are odd. If the sum equals 3, it means that each term in the sum must have been 1, confirming that all three numbers are odd. If we find such a sequence, we immediately return true. If we reach the end of our checks without finding a sequence, we return false.

Iterating through the array and checking each trio of consecutive elements provides us with a clear way to solve this problem.

Solution Approach

The algorithm we use to solve this problem is straightforward linear iteration over the array. We don't need any complex data structures—just the ability to access elements in the array by their index.

The main pattern we utilize is a simple for-loop, which iterates over each element in the array up to the third-to-last element. This is because we need to check each group of three consecutive numbers, and beyond the third-to-last element there are not enough numbers to make up a group of three.

The core logic of the solution is encapsulated in the for-loop:

for i in range(len(arr) - 2):
    if arr[i] % 2 + arr[i + 1] % 2 + arr[i + 2] % 2 == 3:
        return True

As we iterate over the array, we check each group of three consecutive elements. With the expression arr[i] % 2 + arr[i + 1] % 2 + arr[i + 2] % 2, we are essentially summing up the remainders of dividing each of the three consecutive numbers by 2.

If the sum is equal to 3, we hit our target condition: all three numbers must be odd (since the sum of their remainders when divided by 2 is the maximum it could possibly be for three numbers). When this condition is met, we immediately exit the loop and return True.

If we complete the loop without finding three consecutive odd numbers, we exit the loop normally and return False. This happens after the loop has checked up to the third-to-last element without success.

No additional space is required other than the input array, making the space complexity of this algorithm O(1), or constant space. The time complexity is O(n), where n is the length of the array, because we may need to check every element in the array in the worst-case scenario.

Example Walkthrough

Let's consider a small example where the given array is arr = [2, 1, 3, 5, 1]. We're going to walk through this array to look for three consecutive odd numbers.

Starting with the index i = 0, we check the elements at positions 0, 1, and 2. Arr[i] is 2, arr[i+1] is 1, and arr[i+2] is 3. We calculate the remainder of each when divided by 2, which gives us:

• arr[0] % 2 = 2 % 2 = 0
• arr[1] % 2 = 1 % 2 = 1
• arr[2] % 2 = 3 % 2 = 1

Adding these up, we get: 0 + 1 + 1 = 2. Since the sum is not 3, not all of these numbers are odd.

Next, we increment i to 1 and perform the sum of remainders for elements at index 1, 2, and 3. Arr[i] is now 1, arr[i+1] is 3, and arr[i+2] is 5. The remainders are:

• arr[1] % 2 = 1 % 2 = 1
• arr[2] % 2 = 3 % 2 = 1
• arr[3] % 2 = 5 % 2 = 1

The sum this time is 1 + 1 + 1 = 3. Each of the terms in the sum is 1, which indicates that all three numbers (1, 3, 5) are odd, and they are consecutive in the array. Therefore, we have found a sequence that meets the criteria and we return True.

In this case, our search would terminate early, and we would not need to continue iterating to the end of the array. If, however, no such sequence of three consecutive odd numbers existed, we would finish the for-loop without returning True and would instead return False at the end.

This walkthrough demonstrates the described solution approach: linear iteration and conditional checking without any need for complex algorithms or data structures.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input array. This complexity arises because the code uses a single loop that iterates through the array from the beginning to n-3. The loop has a constant time check arr[i] % 2 + arr[i + 1] % 2 + arr[i + 2] % 2 == 3 inside it, which does not depend on the size of the input, therefore not affecting the overall linear time complexity.

The space complexity of the code is O(1), indicating that the space required is constant and does not depend on the input array size. This is due to the fact that the method only uses a fixed number of single-value variables (i) and does not allocate any additional memory that scales with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.