Prefix Sum and Sliding Window 04

Given an array containing N integers and a positive integer K, find the length of the longest sub array with sum of the elements divisible by the given values k.

Problem link :- click here

Code

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//LONGEST SUBARRAY WITH SUM DIVISIBLE BY K

public class Prefix_sum__Sliding_window_04
{
	static int longestSubarrayWithSumDivisibleByK(int arr[], int k)
	{
		
		/*
		 	*) This problem is similar to problem 2 where we have used the psa(prefix sum array).
		 	*) Here instead of `psa` we are creating `modarr` 
		 		such that modarr[i] = psa[i] % k
		 	*) If any element in `modarr` is == 0, then there is a sub-array starting from index 0
		 		having sum of elements divisible by k.
		 	*) How to verify sub-arrays which doesn't start with index 0?
		 	*) Consider a example: 	arr = {2, 7,   6,   1,    4,   5}			k = 3
		 				psa = {2, 9, 15, 16, 20, 25}
		 			     modarr = {2, 0,   0,   1,    2,   1}
		             If there is a sub-array with sum divisible by k, then modarr will have some elements repeated.
		 	    i.e.., 	8%3  =  2    and 	26 % 3 = 2
		 					  (18 + 8) % 3 = 2
		 	    If we remove 8 then we will get a sub-array of sum = 18 which is divisible by 3.
		 	*) We will store the first occurrence of a modulus in a hashMap with its index, 
		 		So that we can find the length of the sub-array.
		 */

		
		//	Creating modarr 
		int modarr[] = new int[arr.length];
		int sum = 0;
		for(int i=0; i<arr.length; i++)
		{
			sum += arr[i];
			
			modarr[i] = ((sum % k) + k) % k;
		}
		
		int max = 0;
		Map<Integer, Integer> hp = new HashMap<>();
		
		for(int i=0; i<arr.length; i++)
		{
			//	Here we don't check if  max < i + 1. Because as we go in the array `i` only increases
			//	and we start with max = 0. 
			if(modarr[i] == 0)
				max = i + 1;	// i + 1   ----> Number of elements in the sub-array whose sum is divisible by k
			
			//	Repeating modulus
			if( hp.containsKey(modarr[i]) )
			{
				if(max < ( i - hp.get(modarr[i])  ) )
					max = i - hp.get(modarr[i]);
			}
			else
				hp.put(modarr[i], i);	// Adding the new modulus to the hashMap
		}
		
		return max;
	}
	
	static int longestSubarrayWithSumDivisibleByK2(int[] arr, int k)
	{
		/*
		 	In this function instead of storing the modulus values in an array we will use it on the go.
		 */
		
		Map<Integer, Integer> hp = new HashMap<>();
		int max = 0;
		
		int sum = 0;
		for(int i=0; i<arr.length; i++)
		{
			sum += arr[i];
			int mod = ((sum % k) + k) % k;
			
			if(mod == 0)
				max = i + 1;
			
			if( hp.containsKey(mod) )
			{
				if(max < (i - hp.get(mod)) )
					max = i - hp.get(mod);
			}
			else
				hp.put(mod, i);
		}
		
		return max;
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		//	Taking size of array and array as input from the user
		System.out.print("Enter the size of the array : ");
		int n = s.nextInt();
		
		int[] arr = new int[n];
		System.out.println("Enter the array elements : ");
		for(int i=0; i<n; i++)
			arr[i] = s.nextInt();
		
		System.out.print("Enter the the value of k : ");
		int k = s.nextInt();
		
		System.out.println(longestSubarrayWithSumDivisibleByK2(arr, k));
	}

}