Skip to content

4063. Longest Subarray Divisible by K with At Most One Negation I

DifficultyMedium

Description

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

A subarray is valid if its sum is divisible by k, or can become divisible by k by negating one element within that subarray.

Negating an element means replacing its value x with -x.

Return the length of the longest valid subarray. If no valid subarray exists, return 0.

A subarray is a contiguous, non-empty sequence of elements within an array.

 

Example 1:

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

Output: 3

Explanation:

  • The sum of the entire array is 7, and 7 % 3 = 1, so it is not divisible by k = 3.
  • Negating nums[2] = 2 changes the sum to 4 + 1 − 2 = 3, which is divisible by k.
  • Therefore, the entire array is a valid subarray, giving a length of 3.

Example 2:

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

Output: 2

Explanation:

  • The sum of the entire array is 12, and negating any one of its elements does not make its sum divisible by 7.
  • However, the subarray [3, 4] has a sum of 7, which is divisible by k = 7 without any negation.
  • Therefore, the longest valid subarray has a length of 2.

Example 3:

Input: nums = [2,2,5], k = 6

Output: 2

Explanation:

  • The sum of the entire array is 9, and negating any one of its elements does not make its sum divisible by 6.
  • The subarray [2, 2] has a sum of 4. Negating either element changes it to [-2, 2] or [2, -2], both of which have a sum of 0.
  • Therefore, the longest valid subarray has a length of 2.

 

Constraints:

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

Solutions

Solution 1: Enumerate the Negated Index

Thinking

A subarray sum is divisible by \(k\) exactly when the prefix sums at its two ends are congruent modulo \(k\). Enumerating every subarray and then every element inside it is about \(O(n^3)\). Since \(n\le 1000\), the search has to drop an order of magnitude.

Negating \(x\) decreases the sum of every subarray that contains it by \(2x\), and leaves every other subarray unchanged. There are \(n\) choices for the negated index, plus the choice of negating nothing. Each choice only needs the longest subarray whose sum is divisible by \(k\).

Each prefix residue modulo \(k\) keeps the first index where it appears. Meeting that residue again makes an earlier left end a longer subarray. A subarray that misses the negated index was already counted on the original array.

After \(\textit{nums}[i]\) is negated, every subarray that contains index \(i\) loses \(2\times\textit{nums}[i]\), and every subarray that misses \(i\) keeps its sum. Run the divisible-subarray search on the original array and again after negating each index in turn. The answer is the maximum of those lengths.

The scan keeps the prefix sum modulo \(k\), with the residue folded into \([0, k)\). Each residue keeps the first index where it appears, and residue \(0\) starts at index \(-1\). At index \(i\), if the current residue was seen at index \(j\), then the sum of \(\textit{nums}[j+1..i]\) is divisible by \(k\) and the length is \(i-j\). Python, Java, Go, and TypeScript store those indices in a hash map. C++ uses an array of length \(k\), indexed by the residue, and passes the negated index as a parameter.

The time complexity is \(O(n^2)\) and the space complexity is \(O(n)\). C++ resets that array on every scan, so its time complexity is \(O(n(n+k))\) and its space complexity is \(O(k)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestSubarray(self, nums: list[int], k: int) -> int:
        def f(nums: list[int], k: int) -> int:
            d = {0: -1}
            s = res = 0
            for i, x in enumerate(nums):
                s = (s + x) % k
                if s in d:
                    res = max(res, i - d[s])
                else:
                    d[s] = i
            return res

        ans = f(nums, k)
        for i, x in enumerate(nums):
            nums[i] = -x
            ans = max(ans, f(nums, k))
            nums[i] = x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int longestSubarray(int[] nums, int k) {
        int ans = f(nums, k);
        for (int i = 0; i < nums.length; ++i) {
            nums[i] = -nums[i];
            ans = Math.max(ans, f(nums, k));
            nums[i] = -nums[i];
        }
        return ans;
    }

    private int f(int[] nums, int k) {
        Map<Integer, Integer> d = new HashMap<>();
        d.put(0, -1);
        int s = 0, res = 0;
        for (int i = 0; i < nums.length; ++i) {
            s = ((s + nums[i]) % k + k) % k;
            if (d.containsKey(s)) {
                res = Math.max(res, i - d.get(s));
            } else {
                d.put(s, i);
            }
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int longestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> d(k, -2);

        auto f = [&](int skip) {
            fill(d.begin(), d.end(), -2);
            d[0] = -1;
            int s = 0, res = 0;
            for (int i = 0; i < n; ++i) {
                int x = i == skip ? -nums[i] : nums[i];
                s = (s + x) % k;
                if (s < 0) {
                    s += k;
                }
                if (d[s] != -2) {
                    res = max(res, i - d[s]);
                } else {
                    d[s] = i;
                }
            }
            return res;
        };

        int ans = f(-1);
        for (int i = 0; i < n; ++i) {
            ans = max(ans, f(i));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func longestSubarray(nums []int, k int) int {
    f := func(nums []int) int {
        d := map[int]int{0: -1}
        s, res := 0, 0
        for i, x := range nums {
            s = (s + x) % k
            if s < 0 {
                s += k
            }
            if j, ok := d[s]; ok {
                res = max(res, i-j)
            } else {
                d[s] = i
            }
        }
        return res
    }

    ans := f(nums)
    for i, x := range nums {
        nums[i] = -x
        ans = max(ans, f(nums))
        nums[i] = x
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function longestSubarray(nums: number[], k: number): number {
    const f = (nums: number[]): number => {
        const d = new Map<number, number>([[0, -1]]);
        let s = 0,
            res = 0;
        for (let i = 0; i < nums.length; ++i) {
            s = (s + nums[i]) % k;
            if (s < 0) {
                s += k;
            }
            if (d.has(s)) {
                res = Math.max(res, i - d.get(s)!);
            } else {
                d.set(s, i);
            }
        }
        return res;
    };

    let ans = f(nums);
    for (let i = 0; i < nums.length; ++i) {
        nums[i] = -nums[i];
        ans = Math.max(ans, f(nums));
        nums[i] = -nums[i];
    }
    return ans;
}

Comments