Continuous Subarray Sum

Given an integer array and an integer k, determine whether the array contains a continuous subarray of size at least two whose sum is a multiple of k. In other words, check if there exists a contiguous sequence of elements (with length ≥ 2) such that their sum can be expressed as n*k for some integer n. Note that when k is 0, the problem changes to finding a contiguous subarray whose sum is exactly 0.

Example 1: For the array [23, 2, 4, 6, 7] and k = 6, the subarray [2, 4, 6] has a sum of 12 which is 2×6, so the answer is true.

Example 2: For the array [23, 2, 6, 4, 7] and k = 13, no valid subarray exists, hence the answer is false.

The efficient solution uses prefix sums combined with modulo operations. Using a hash map (or similar data structure), we can store the remainder when the prefix sum is divided by k and check for repeated remainders with an interval of at least 2 between them. This approach runs in linear time.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains two integers n and k, where n is the number of elements in the array and k is the divisor.
• The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single line to stdout containing true if there exists a continuous subarray of size at least 2 whose sum is a multiple of k, or false otherwise.

5 6
23 2 4 6 7

true