Skip to content

3972. Valid Subarrays With Matching Sum Digits II πŸ”’

Description

You are given an integer array nums and an integer digit x.

A subarray nums[l..r] is considered valid if the sum of its elements satisfies both of the following conditions:

  • The first digit of the sum is equal to x.
  • The last digit of the sum is equal to x.

Return the number of valid subarrays.

 

Example 1:

Input: nums = [1,100,1], x = 1

Output: 4

Explanation:

The valid subarrays are:

  • nums[0..0]: sum = 1
  • nums[0..1]: sum = 1 + 100 = 101
  • nums[1..2]: sum = 100 + 1 = 101
  • nums[2..2]: sum = 1

Thus, the answer is 4.

Example 2:

Input: nums = [1], x = 2

Output: 0

Explanation:

The only subarray is nums[0..0] with a sum of 1, which does not satisfy the conditions.

Thus, the answer is 0.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= x <= 9

Solutions

Solution 1

Thinking

Part I enumerated subarrays; now \(n\le 10^5\). The last digit of a sum is a prefix-sum difference modulo \(10\); the first digit depends on magnitude and is harder.

Bucket prefix sums by residue modulo \(10\). For each right end, count left ends that match the last-digit condition and whose range sum has leading digit \(x\), after splitting by order of magnitude.

This directory has no implemented solution yet; the walkthrough stops at prefix sums modulo \(10\) plus a leading-digit filter.

1


1


1


1

Comments