FastPrep
Problem · Array

Count Sawtooth Subarrays

Learn this problem
● EasyHudson River Trading logoHudson River TradingFULLTIMENEW GRADINTERNOA

Problem statement

A sawtooth sequence alternates between even and odd values: every adjacent pair contains one even value and one odd value.

Given an integer array arr, count the number of contiguous subarrays that are sawtooth sequences. Every non-empty subarray is eligible, and a single-element subarray is always valid.

Function

countSawtoothSubarrays(arr: int[]) → long

Examples

Example 1

arr = [1,3,5,7,9]return = 5

Every pair of adjacent values is odd-odd, so no subarray of length at least 2 is valid. The five single-element subarrays are valid, so the result is 5.

Example 2

arr = [1,2,1,2,1]return = 15

The entire array alternates parity, so all 5 * 6 / 2 = 15 contiguous subarrays are valid.

Example 3

arr = [1,2,3,7,6,5]return = 12

The only parity break is the adjacent odd pair 3, 7. The alternating runs are [1, 2, 3] and [7, 6, 5]; each run contributes 3 * 4 / 2 = 6 valid subarrays, for a total of 12.

More Hudson River Trading problems

drafts saved locally
public long countSawtoothSubarrays(int[] arr) {
    // write your code here
}
arr[1,3,5,7,9]
expected5
checking account