Skip to content

3969. Valid Subarrays With Matching Sum Digits I

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 <= 1500
  • 1 <= nums[i] <= 109
  • 1 <= x <= 9

Solutions

Solution 1: Enumeration

We can enumerate the left endpoint \(l\) of the subarray, and for each \(l\), we enumerate the right endpoint \(r\) in the range \([l, n)\), and calculate the sum of \(nums[l..r]\). If it satisfies the conditions, the answer is increased by one.

The time complexity is \(O(n^2)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countValidSubarrays(self, nums: list[int], x: int) -> int:
        n = len(nums)
        ans = 0
        for l in range(n):
            s = 0
            for r in range(l, n):
                s += nums[r]
                if s % 10 == x and int(str(s)[0]) == x:
                    ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countValidSubarrays(int[] nums, int x) {
        int n = nums.length;
        int ans = 0;

        for (int l = 0; l < n; l++) {
            long s = 0;
            for (int r = l; r < n; r++) {
                s += nums[r];
                if (s % 10 == x && Long.toString(s).charAt(0) - '0' == x) {
                    ans++;
                }
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countValidSubarrays(vector<int>& nums, int x) {
        int n = nums.size();
        int ans = 0;

        for (int l = 0; l < n; ++l) {
            long long s = 0;
            for (int r = l; r < n; ++r) {
                s += nums[r];
                if (s % 10 == x && to_string(s)[0] - '0' == x) {
                    ++ans;
                }
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func countValidSubarrays(nums []int, x int) (ans int) {
    n := len(nums)

    for l := 0; l < n; l++ {
        var s int64
        for r := l; r < n; r++ {
            s += int64(nums[r])
            if s%10 == int64(x) && int(strconv.FormatInt(s, 10)[0]-'0') == x {
                ans++
            }
        }
    }

    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function countValidSubarrays(nums: number[], x: number): number {
    const n = nums.length;
    let ans = 0;

    for (let l = 0; l < n; l++) {
        let s = 0;

        for (let r = l; r < n; r++) {
            s += nums[r];

            if (s % 10 === x && Number(s.toString()[0]) === x) {
                ans++;
            }
        }
    }

    return ans;
}

Comments