Longest Subarray with Sum Divisible by K
Inmobi's ad-serving infrastructure often processes sequences of events or metrics. Sometimes, we need to identify patterns or segments within these sequences that satisfy certain criteria. For instance, analyzing a sequence of daily revenue changes, we might want to find the longest continuous period where the cumulative change in revenue is a multiple of a certain threshold K. This problem asks you to find the longest subarray whose sum is perfectly divisible by a given integer K.
Given an integer array nums and an integer k, implement a function longestSubarrayDivisibleByK that returns the length of the longest subarray whose elements sum up to a value divisible by k.
nums: An array of integers.k: An integer representing the divisor.k. If no such subarray exists (other than an empty subarray, which has length 0), return 0.k (where k != 0).k will always be a positive integer.nums can contain positive, negative, or zero integers.Examples
Example 1
Input:
nums = [2, 7, 6, 1, 4, 5], k = 3
Output:
4
Note:
The subarray [7, 6, 1, 4] from index 1 to 4 sums to 18, which is divisible by 3. Its length is 4. No longer subarray satisfies the condition.
Example 2
Input:
nums = [1, 2, 3, 4, 5], k = 10
Output:
4
Note:
The subarray [1, 2, 3, 4] from index 0 to 3 sums to 10, which is divisible by 10. Its length is 4.
Example 3
Input:
nums = [5, 0, 5, 0], k = 5
Output:
4
Note:
The entire array [5, 0, 5, 0] sums to 10, which is divisible by 5. Its length is 4.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= 10^5k for all valid inputs.Loading editor...