Imagine you have a box full of toys, and you're playing a game where you
pick a group of toys and then add their numbers together. Your goal is to
find the largest group of toys whose total number can be evenly split
among your friends. This is like dividing a number by another number, and
there’s no extra toys left (no remainder).
In this game, the number of toys is called the **sum** of the group, and
the number of friends you're splitting the toys between is called **K**.
The task is to find the **longest group** of toys (longest subarray) where
the total number of toys (the sum of the subarray) can be perfectly split
between K friends.
### Steps to Solve this in Java
1. **Array and Subarray:**
- You have an array (or list) of numbers, like `[2, 7, 6, 1, 4, 5]`.
- A **subarray** is any continuous group of numbers from that array. For
example, from the array `[2, 7, 6, 1, 4, 5]`, the subarray `[7, 6]` is a group
of two numbers.
2. **Sum Divisible by K:**
- We need to find a subarray whose sum is divisible by `K`. If the sum of
a group of numbers can be divided by `K` with no leftover, it means the
result of that division is a whole number.
- For example, if K = 3, the subarray sum should give no remainder
when divided by 3. For instance, if the sum is 6, then `6 % 3 = 0`.
3. **Using a Trick to Solve This:**
- Here's the tricky part: instead of checking all possible groups of
numbers (which can be slow), we use a **prefix sum** and **modulus** to
find out if a subarray sum is divisible by K.
- A **prefix sum** is the sum of numbers from the start of the array to a
certain position. For example, in the array `[2, 7, 6]`, the prefix sum up to
`6` is `2 + 7 + 6 = 15`.
4. **How Does the Modulus Help?**
- When you take the remainder of a number after dividing by K, it helps
to find out if two parts of the array have the same remainder. If two prefix
sums have the same remainder when divided by K, the subarray between
these two positions has a sum divisible by K!
### Code Explanation (Longest Subarray with Sum Divisible by K)
```java
import [Link];
public class LongestSubarrayDivisibleByK {
public static int longestSubarray(int[] arr, int K) {
// HashMap to store the remainder and the first index where it
occurred
HashMap<Integer, Integer> remainderMap = new HashMap<>();
int maxLength = 0;
int currentSum = 0;
// Initialize with remainder 0 at index -1 to handle cases when the
subarray starts from index 0
[Link](0, -1);
// Iterate through the array
for (int i = 0; i < [Link]; i++) {
currentSum += arr[i]; // Update the current sum
// Find the remainder of the current sum when divided by K
int remainder = currentSum % K;
// If remainder is negative, adjust it to be in the range [0, K-1]
if (remainder < 0) {
remainder += K;
// If this remainder has been seen before
if ([Link](remainder)) {
// Calculate the length of the subarray
int previousIndex = [Link](remainder);
int subarrayLength = i - previousIndex;
// Update maxLength if this subarray is longer
maxLength = [Link](maxLength, subarrayLength);
} else {
// If this is the first time we see this remainder, store the index
[Link](remainder, i);
return maxLength; // Return the length of the longest subarray
public static void main(String[] args) {
int[] arr = {2, 7, 6, 1, 4, 5};
int K = 3;
[Link]("Longest subarray length: " +
longestSubarray(arr, K)); // Output: 4
```
### Step-by-Step Explanation:
1. **Initialize a HashMap:**
- The map (`remainderMap`) keeps track of remainders of sums when
divided by K and stores the earliest index where each remainder occurs.
- We start by putting `remainder 0` at index `-1`. This helps handle
cases when a subarray starts from the very beginning of the array.
2. **Loop Through the Array:**
- For each element in the array, we calculate the cumulative sum (or
prefix sum).
- Then, we calculate the remainder when this sum is divided by `K`.
3. **Adjust Negative Remainders:**
- If the remainder is negative (like if the sum is negative), we adjust it by
adding K to make it positive.
4. **Check if the Remainder Exists in the Map:**
- If the remainder has been seen before, it means the sum of the
elements between the two indices where this remainder occurred is
divisible by `K`.
- Calculate the length of this subarray and update the maximum length
if it's the longest one found so far.
5. **Store New Remainders:**
- If the remainder has not been seen, store it along with the current
index.
6. **Return the Maximum Length:**
- Finally, the longest subarray whose sum is divisible by `K` is returned.
### Example Walkthrough:
For the array `{2, 7, 6, 1, 4, 5}` and K = 3:
1. Start with `currentSum = 0`.
2. At index `0`, add `2`: `currentSum = 2`, remainder = `2 % 3 = 2`.
Store remainder `2` at index 0.
3. At index `1`, add `7`: `currentSum = 9`, remainder = `9 % 3 = 0`.
Subarray from index `0 to 1` has sum `9`, which is divisible by `K`.
Length = 2.
4. At index `2`, add `6`: `currentSum = 15`, remainder = `15 % 3 = 0`.
Subarray from index `0 to 2` has sum `15`. Length = 3.
5. Continue and find longer subarrays, ending with the longest subarray of
length `4`.
### Conclusion:
We used a trick with remainders to efficiently find the longest subarray
whose sum is divisible by K. The **HashMap** helps keep track of where
each remainder occurs, making it easier to quickly check if a valid
subarray exists.
