How to usePrefix Sum in Javascript

We can use prefix sums to efficiently calculate subarray sums. By storing the cumulative sum of elements up to each position, you can quickly determine the sum of any subarray. To find the largest subarray divisible by ‘k’, you track the prefix sums modulo ‘k’ and store the indices where each remainder is first encountered.

Javascript

function largestSubarraySumDivisibleByK(arr, k) { 
    const prefixSums = [0]; 
    let currentSum = 0; 
    let maxLength = 0; 
  
    for (let num of arr) { 
        currentSum = (currentSum + num) % k; 
        prefixSums.push(currentSum); 
    } 
  
    const remainderIndices = {}; 
  
    for (let i = 0; i < prefixSums.length; i++) { 
        if (remainderIndices 
            .hasOwnProperty(prefixSums[i])) { 
            maxLength = Math.max(maxLength, 
                i - remainderIndices[prefixSums[i]]); 
        } else { 
            remainderIndices[prefixSums[i]] = i; 
        } 
    } 
  
    return maxLength; 
} 
  
const arr = [7, 1, 3, 2, 9]; 
const k = 3; 
console.log(largestSubarraySumDivisibleByK(arr, k));

Output

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