Longest Subarray Divisible by K with At Most One Negation II - Video Solutions
Longest Subarray Divisible by K with At Most One Negation II | Maths + Prefix Map + Binary Search
Longest Subarray Divisible by K with At Most One Negation II - Video Solution
Watch the video solution for Longest Subarray Divisible by K with At Most One Negation II, a hard level problem. This walkthrough by Manjeet Dhayal has 88 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 byk = 3. - Negating
nums[2] = 2changes the sum to4 + 1 − 2 = 3, which is divisible byk. - 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 byk = 7without 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 <= 105āāāāāāā-105 <= nums[i] <= 1051 <= k <= 3000āāāāāāā