Problem
Welcome to the Modular Maze Solver, where you become an adventurer tasked with traversing a maze constructed from numbers. In this world, each path you explore is governed by the rules of modular arithmetic. Your mission: determine if a contiguous subarray exists within a list of integers such that the sum of its elements, when divided by a given modulus, results in a remainder equal to a specified target number. Here's how to tackle the challenge: 1. Begin by understanding the inputs: a sequence of integers, a target number, and a modulus value. 2. Explore all possible contiguous subarrays within the sequence. 3. For each subarray, calculate the sum of its elements and apply the modulus operation. 4. Check if the result equals the target number. If such a subarray exists, your mission is accomplished! Consider the example where your list is [3, 1, 4, 1, 5], the target is 2, and the modulus is 5. The subarray [1, 4] sums to 5, which is 0 mod 5, hence does not meet the target. However, subarray [4, 1] sums to 5, and 5 mod 5 equals 0, which is not our target of 2. Continue exploring to find valid solutions.
- Consider employing a sliding window technique or prefix sums to optimize the search for subarrays.
- A hash map might be a valuable tool to keep track of previously seen sums and their mod results.
- Watch out for edge cases, such as when the list is empty or contains only one element.
- Remember, optimization is key: aim to reduce time complexity by avoiding unnecessary recalculations.
Input format
The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers, the elements of the array. The third line contains two integers: m and t, the divisor and the target modulo sum respectively.
Output format
Output 'YES' if there exists a contiguous subarray whose sum modulo m is equal to t, otherwise output 'NO'.
Constraints
1 <= n <= 10^5, 1 <= array[i] <= 10^9, 1 <= m <= 10^5, 0 <= t < m
Sample input
5 3 1 4 1 5 7 4
Sample output
YES