Longest Subarray Divisible by K with At Most One Negation I

Problem Statement

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 (replacing x with -x).

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

---

Input / Output

Input: nums = [4,1,2], k = 3 Output: 3 Explanation: Sum 7; negate 2 → 4 + 1 - 2 = 3, divisible by 3. Input: nums = [5,3,4], k = 7 Output: 2 Explanation: [3,4] sums to 7. Input: nums = [2,2,5], k = 6 Output: 2 Explanation: [2,2] → negate one → 0, divisible by 6.

---

Constraints

1 ≤ nums.length ≤ 1000 -10^5 ≤ nums[i] ≤ 10^5 1 ≤ k ≤ 10^5

---

Understanding the Problem

Negating x changes the sum from S to S - 2x. So a subarray is valid when:

S ≡ 0 (mod k) — no negation S - 2x ≡ 0 (mod k) ⇔ 2x ≡ S (mod k) — for some x in the subarray