//User function Template for Java

class Solution{

    int longSubarrWthSumDivByK(int a[], int n, int k)

    { int sum = 0;

        int maxLength = 0;

      HashMap<Integer, Integer> remainderMap = new HashMap<>();

        for (int i = 0; i < n; i++) {

            sum += a[i];

            // Calculate the remainder when divided by K

            int remainder = (sum % k + k) % k;

            // If remainder is 0, update maxLength to current length

            if (remainder == 0) {

                maxLength = i + 1;

            }

            // If remainder is seen before, update maxLength with the difference of current index and previous index

            else if (remainderMap.containsKey(remainder)) {

                maxLength = Math.max(maxLength, i - remainderMap.get(remainder));

            }

            // If remainder is not seen before, add it to the HashMap with its index

            else {

                remainderMap.put(remainder, i);

            }

        }

        return maxLength;

    }

}