Given an integer array nums and an integer k, return true if nums has a subarray of at least two elements whose sum is a multiple of k.
Hard
Determine if a given array contains a subarray of at least two elements whose sum is a multiple of a specified number k.
An array is considered to have a "good subarray" if there exists at least one subarray (consisting of two or more elements) such that the sum of the elements in this subarray is a multiple of k.
For example, the array [23, 2, 4, 7] with k = 6 has a "good subarray" ([2, 4]), as the sum 6 is a multiple of k = 6. The array [5, 0, 0, 0] with k = 3 also has a "good subarray" ([0, 0]), since the sum is 0, and 0 is a multiple of 3.
Examples
nums = [23, 2, 4, 7], k = 6 output: true nums = [5, 0, 0, 0], k = 3 output: true nums = null, k = 1 output: false
In these examples, the output is true if there exists a "good subarray" in the given array nums for the specified k, and false otherwise.
Our solution processes the input array by iterating through it while maintaining a hash map (remainder_index_map) of remainders and their corresponding indices. For each element in the array, we accumulate the sum (sum_so_far) and compute the remainder when divided by k. We check if this remainder has been encountered before in the hash map.
- If the remainder is not in the hash map, we store the current index associated with this remainder.
- If the remainder has been seen before, we calculate the distance between the current index and the index of the previously seen remainder. If this distance is greater than or equal to the minimum subarray length (
MIN_GOOD_SUBARRAY_LIMIT), we returnTrue, indicating that a subarray with the required properties exists.
If the loop completes without finding such a subarray, we return False.
The use of a hash map ensures that each element is processed efficiently, as it allows constant-time lookups and insertions.
Time Complexity: The solution has a time complexity of O(n), where n is the number of elements in the array. This is because we iterate through the array once, performing constant-time operations (hash map lookups and insertions) for each element.
Space Complexity: The solution uses O(n) space for the hash map that stores the remainders and their indices. In the worst case, all remainders are unique, resulting in the hash map containing n entries.
Let’s say you are given an integer array nums and an integer k. Return true if nums has a subarray where its length is at least two, and the sum of the elements in the subarray is a multiple of k.
Watch Neeraj, a Senior Engineering Manager, give his answer to this software engineering interview question.
Related questions
Given an array of n integers and a number k, find the maximum number of elements whose sum is less than k, and return their sum.Given an array of integers and a number N, find the length of the longest contiguous subarray such that the difference between any two elements in the subarray is less than N.Given an array of integers and an integer k, find the kth largest element in the array.Related courses
