Frontend School

Longest Subarray with Sum Divisible by K

DSA
medium

Longest Subarray with Sum Divisible by K

Medium
Arrays
Hashing

Overview

Inmobi's ad-serving infrastructure often processes sequences of events or metrics. Sometimes, we need to identify patterns or segments within these sequences that satisfy certain criteria. For instance, analyzing a sequence of daily revenue changes, we might want to find the longest continuous period where the cumulative change in revenue is a multiple of a certain threshold K. This problem asks you to find the longest subarray whose sum is perfectly divisible by a given integer K.

What you need to do / Task

Given an integer array nums and an integer k, implement a function longestSubarrayDivisibleByK that returns the length of the longest subarray whose elements sum up to a value divisible by k.

Input & output

  • Input:
    • nums: An array of integers.
    • k: An integer representing the divisor.
  • Output:
    • An integer representing the maximum length of a subarray whose sum is divisible by k. If no such subarray exists (other than an empty subarray, which has length 0), return 0.

Clarifications

  • A subarray is a contiguous part of an array.
  • The sum of an empty subarray is 0, which is divisible by any k (where k != 0).
  • k will always be a positive integer.
  • nums can contain positive, negative, or zero integers.

Examples

1

Example 1

Input:

nums = [2, 7, 6, 1, 4, 5], k = 3

Output:

4

Note:

The subarray [7, 6, 1, 4] from index 1 to 4 sums to 18, which is divisible by 3. Its length is 4. No longer subarray satisfies the condition.

2

Example 2

Input:

nums = [1, 2, 3, 4, 5], k = 10

Output:

4

Note:

The subarray [1, 2, 3, 4] from index 0 to 3 sums to 10, which is divisible by 10. Its length is 4.

3

Example 3

Input:

nums = [5, 0, 5, 0], k = 5

Output:

4

Note:

The entire array [5, 0, 5, 0] sums to 10, which is divisible by 5. Its length is 4.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= 10^5
  • The sum of any subarray will fit within a standard 32-bit integer type (or 64-bit for languages that use it automatically, like JS/TS numbers).

What interviewers evaluate

  • Correctness: The solution must correctly identify the longest subarray whose sum is divisible by k for all valid inputs.
  • Efficiency: The solution should achieve optimal time and space complexity, typically O(N) time and O(N) space.
  • Code Quality: Readability, maintainability, and proper use of data structures.
  • Edge Cases: Handling cases like arrays with negative numbers, zeros, and scenarios where no non-empty subarray satisfies the condition.

Loading editor...