Welcome to Subscribe On Youtube

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$.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}

  • 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;
}

All Problems

All Solutions