Longest Subarray with Sum Divisible by Given Number in Array with JavaScript
Given an array of integers, the task is to find the longest subarray whose sum is divisible by a given number.
Example:
Input:[4, 5, 0, -2, -3, 1], k = 5Output:Length = 6
Below are the approaches to find the longest subarray with sum divisible by a given number using JavaScript:
Table of Content
- Brute Force Approach
- Prefix Sum and Hashing
Brute Force Approach
In this approach, The brute force approach involves checking all possible subarrays and finding the longest subarray whose sum is divisible by k. This code iterates through all subarrays of the input array, calculating their sums. When a sum is divisible by the given number k, it updates ‘maxLength’ if the current subarray length is greater. Finally, it returns the length of the longest subarray with a sum divisible by k.
Example: The example below shows how to find the longest subarray with sum divisible by a given number using JavaScript.
function longestSubarrayDivisibleByK(arr, k) {
let maxLength = 0;
for (let i = 0; i < arr.length; i++) {
let sum = 0;
for (let j = i; j < arr.length; j++) {
sum += arr[j];
if (sum % k === 0) {
maxLength = Math.max(maxLength, j - i + 1);
}
}
}
return maxLength;
}
const arr = [4, 5, 0, -2, -3, 1];
const k = 5;
console.log(longestSubarrayDivisibleByK(arr, k));
Output
6
Time Complexity: O(n^2)
Space Complexity: O(1)
Prefix Sum and Hashing
This approach involves using prefix sum and hashing to efficiently find the longest subarray whose sum is divisible by k. This code utilizes the prefix sum technique and hashing to efficiently find the longest subarray with a sum divisible by k. It maintains a map to store the remainder of the current prefix sum divided by k, updating the ‘maxLength’ when encountering a matching remainder. Finally, it returns the length of the longest subarray.
Example: The example below shows how to find the longest subarray with sum divisible by a given number using Prefix Sum and Hashing.
function longestSubarrayDivisibleByK(arr, k) {
let maxLength = 0;
let currSum = 0;
const map = new Map();
map.set(0, -1);
for (let i = 0; i < arr.length; i++) {
currSum += arr[i];
const remainder = currSum % k;
if (map.has(remainder)) {
maxLength = Math.max(maxLength, i - map.get(remainder));
} else {
map.set(remainder, i);
}
}
return maxLength;
}
const arr = [4, 5, 0, -2, -3, 1];
const k = 5;
console.log(longestSubarrayDivisibleByK(arr, k));
Output
6
Time Complexity: O(n)
Space Complexity: O(n)