Skip to content

4075. Longest Resilient Subarray I

DifficultyMedium

Description

You are given an integer array nums and an integer k.

A subarray is resilient if, for every position in it, deleting the element at that position leaves the remaining elements with a sum divisible by k.

For a subarray of length 1, the remaining sum is 0, which is divisible by k.

Return the length of the longest resilient subarray.

 

Example 1:

Input: nums = [2,4,6,3], k = 2

Output: 3

Explanation:

The subarray [2, 4, 6] sums to 12. Deleting 2, 4, or 6 leaves a sum of 10, 8, or 6, respectively, each of which is divisible by 2. Therefore, the answer is 3.

Example 2:

Input: nums = [1,4,7,1], k = 3

Output: 4

Explanation:

The subarray [1, 4, 7, 1] sums to 13. Deleting the first 1, the 4, the 7, or the last 1 leaves a sum of 12, 9, 6, or 12, respectively, each of which is divisible by 3. Therefore, the answer is 4.

Example 3:

Input: nums = [5,5,4,8], k = 4

Output: 2

Explanation:

The subarray [5, 5] is not resilient, since deleting either 5 leaves a sum of 5, which is not divisible by 4.

The subarray [4, 8] sums to 12. Deleting 4 or 8 leaves a sum of 8 or 4, respectively, each of which is divisible by 4. Therefore, the answer is 2.

 

Constraints:

  • 1 <= nums.length <= 2500
  • 1 <= nums[i] <= 105
  • 1 <= k <= 105

Solutions

Solution 1: Congruent Runs

Thinking

A subarray can be as long as \(2500\). Enumerating every interval and then checking the sum after each deletion is cubic, which is too much for this limit.

Requiring \(\textit{sum}-a_i\) to be divisible by \(k\) at every index means every \(a_i\) is congruent to \(\textit{sum}\) modulo \(k\). All elements in the subarray therefore share one residue \(r\), and the length \(L\) must also satisfy \((L-1)r\equiv 0\pmod{k}\).

Equal residues form contiguous runs. Inside a run the length grows by \(1\), and the condition depends only on that length and \(r\), so one pass over each run records every feasible length.

Reduce every element modulo \(k\). Equal residues form contiguous runs. Let \(r\) be the residue of the current run and \(\textit{cnt}\) its current length. A run of length \(1\) is always resilient, because the remaining sum is \(0\). Whenever

\[ r\cdot(\textit{cnt}-1)\equiv 0\pmod{k}, \]

the prefix of length \(\textit{cnt}\) is resilient, and the answer is updated with \(\textit{cnt}\). A change of residue starts a new run.

The time complexity is \(O(n)\) and the space complexity is \(O(1)\), where \(n\) is the length of \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def resilientSubarray(self, nums: list[int], k: int) -> int:
        ans = cnt = 0
        for i, x in enumerate(nums):
            x %= k
            if i and nums[i - 1] % k == x:
                cnt += 1
            else:
                cnt = 1
            if x * (cnt - 1) % k == 0:
                ans = max(ans, cnt)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int resilientSubarray(int[] nums, int k) {
        int ans = 0, cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i] % k;
            if (i > 0 && nums[i - 1] % k == x) {
                cnt++;
            } else {
                cnt = 1;
            }
            if (x * (cnt - 1) % k == 0) {
                ans = Math.max(ans, cnt);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int resilientSubarray(vector<int>& nums, int k) {
        int ans = 0, cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i] % k;
            if (i > 0 && nums[i - 1] % k == x) {
                cnt++;
            } else {
                cnt = 1;
            }
            if (x * (cnt - 1) % k == 0) {
                ans = max(ans, cnt);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func resilientSubarray(nums []int, k int) int {
    ans, cnt := 0, 0
    for i, v := range nums {
        x := v % k
        if i > 0 && nums[i-1]%k == x {
            cnt++
        } else {
            cnt = 1
        }
        if x*(cnt-1)%k == 0 {
            ans = max(ans, cnt)
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function resilientSubarray(nums: number[], k: number): number {
    let ans = 0,
        cnt = 0;
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i] % k;
        if (i > 0 && nums[i - 1] % k === x) {
            cnt++;
        } else {
            cnt = 1;
        }
        if ((x * (cnt - 1)) % k === 0) {
            ans = Math.max(ans, cnt);
        }
    }
    return ans;
}

Comments