How to usea Hash Map in Javascript
An efficient approach involves using a hash map to store the prefix sums modulo ‘k’ and their corresponding indices.
Javascript
function largestSubarraySumDivisibleByK(arr, k) { let currentSum = 0; let maxLength = 0; const remainderIndices = { 0: -1 }; for (let i = 0; i < arr.length; i++) { currentSum += arr[i]; const remainder = (currentSum % k + k) % k; if (remainderIndices .hasOwnProperty(remainder)) { maxLength = Math.max(maxLength, i - remainderIndices[remainder]); } else { remainderIndices[remainder] = i; } } return maxLength; } const arr = [7, 1, 3, 2, 9]; const k = 3; console.log(largestSubarraySumDivisibleByK(arr, k)); |
4
JavaScript Program to Find Largest Subarray with a Sum Divisible by k
Finding the largest subarray with a sum divisible by a given integer ‘k’ is a common problem in JavaScript and other programming languages. This task involves identifying a contiguous subarray within an array of integers such that the sum of its elements is divisible by ‘k’ and is as long as possible. This problem is essential in various scenarios, including optimizing algorithms and data processing.
Examples:
Input: arr[] = {7,1,3,2,9} , k = 3
Output: 4
Explanation: The subarray is {1, 3, 2, 9} with sum 15, which is divisible by 3.
Input: arr[] = { 4, 5}, k = 2
Output: 1
Table of Content
- Brute Force Approach
- Using Prefix Sum
- Using a Hash Map