How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Adobe.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Adobe during technical interviews.

Determine if a multiple-sum subarray exists

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine if a multiple-sum subarray exists states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Adobe

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an integer array nums and an integer k, determine whether there exists a contiguous subarray of length at least 2 whose sum is divisible by k; return true if such a subarray exists, otherwise false. If k = 0, interpret the requirement as finding a length ≥2 subarray with sum exactly 0. Explain your approach and analyze time and space complexity. Follow-up: how would you adapt your solution to a streaming setting where nums arrives incrementally?

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine if a multiple-sum subarray exists states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an integer array `nums` and an integer `k`, determine whether there exists a contiguous subarray of length at least 2 whose sum is divisible by `k`. Return `true` if such a subarray exists, otherwise `false`. Special case: if `k = 0`, interpret the requirement as finding a contiguous subarray of length at least 2 whose sum is exactly 0. For the general (k != 0) case, treat `k` by its absolute value: a sum is "divisible by k" if `sum % |k| == 0`. **Examples** - `nums = [23, 2, 4, 6, 7], k = 6` -> `true` (the subarray `[2, 4]` sums to 6, a multiple of 6). - `nums = [23, 2, 6, 4, 7], k = 13` -> `false` (no length-≥2 contiguous subarray has a sum that is a multiple of 13). - `nums = [1, -1, 3], k = 0` -> `true` (the subarray `[1, -1]` sums to exactly 0). - `nums = [0, 1, 0], k = 0` -> `false` (no contiguous subarray of length ≥2 sums to exactly 0). **Approach (prefix sums + hashing).** Two prefix sums with the same value (k = 0 case) or the same remainder mod |k| mark a subarray whose sum is 0 / divisible by k. Store the earliest index at which each remainder (or prefix value) first appears; when the same key is seen again at an index that is at least 2 positions later, a valid subarray exists. Seed the map with `{0: -1}` so that a prefix itself being 0 / divisible counts. This runs in O(n) time and O(min(n, |k|)) space. **Follow-up (streaming).** The same prefix-sum-mod-k hashing works incrementally: maintain the running remainder and the map of first-seen indices as each element arrives, emitting `true` the moment a repeated remainder is found at index distance ≥ 2. Space stays bounded by O(min(n, |k|)) remainders (or O(n) distinct prefix values when k = 0).

Constraints

1 <= nums.length is typical, but the function must also handle an empty array (returns false).
Elements of nums may be negative, zero, or positive.
k may be negative, zero, or positive; for k != 0 use |k| when testing divisibility.
When k = 0, a single element equal to 0 does NOT qualify — the subarray must have length >= 2.

Examples

Input: ([23, 2, 4, 6, 7], 6)

Expected Output: True

Explanation: Subarray [2, 4] (indices 1..2) sums to 6, a multiple of 6.

Input: ([23, 2, 6, 4, 7], 6)

Expected Output: True

Explanation: Subarray [6, 4] sums to 10... but [2, 6, 4] sums to 12, which is a multiple of 6.

Input: ([23, 2, 6, 4, 7], 13)

Expected Output: False

Explanation: No contiguous subarray of length >= 2 has a sum that is a multiple of 13.

Input: ([1, 2, 3], 5)

Expected Output: True

Explanation: Subarray [2, 3] sums to 5, a multiple of 5.

Input: ([5], 5)

Expected Output: False

Explanation: Only one element, so no subarray of length >= 2 exists.

Input: ([], 1)

Expected Output: False

Explanation: Empty array has no subarray of length >= 2.

Input: ([0, 0], 0)

Expected Output: True

Explanation: k = 0: subarray [0, 0] has length 2 and sums to exactly 0.

Input: ([1, -1, 3], 0)

Expected Output: True

Explanation: k = 0: subarray [1, -1] sums to exactly 0.

Input: ([1, 2, 3], 0)

Expected Output: False

Explanation: k = 0: no contiguous subarray of length >= 2 sums to exactly 0.

Input: ([0, 1, 0], 0)

Expected Output: False

Explanation: k = 0: each 0 is a single element; no length-≥2 subarray sums to 0 (the only zero-sum windows have length 1).

Input: ([-1, 2, 9], -3)

Expected Output: False

Explanation: Using |k| = 3: subarray sums are 1, 11, 10 (length >= 2); none is a multiple of 3.

Input: ([6, 0], 6)

Expected Output: True

Explanation: Subarray [6, 0] sums to 6, a multiple of 6.

Hints

A subarray sum equals prefixSum[j] - prefixSum[i]. It is divisible by k exactly when prefixSum[j] and prefixSum[i] leave the same remainder mod |k| (or are equal, when k = 0).
Store the FIRST index at which each remainder (or prefix value) is seen, and require the gap between matching indices to be at least 2 to enforce the length-≥2 rule.
Seed the map with remainder 0 at index -1 so a prefix that is itself divisible by k (a subarray starting at index 0) is detected.
Handle k = 0 separately: track raw prefix sums instead of remainders and look for two equal prefix sums at least 2 indices apart.

Quick Overview