3

For example, given input arr = [4,5,0,-2,-3,1], k = 5, there are 7 subarrays with a sum divisible by 5: [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]. The shortest one is either [5] or [0], both are correct. If there are no answers return an empty array.

This question is similar to leetcode no. 974 but I can't figure out how to apply the same algorithm to this (that one doesn't really account for the length of subarrays). Can someone help (preferably in python). Thank you!

Dave
  • 7,460
  • 3
  • 26
  • 39
Nathan
  • 350
  • 1
  • 2
  • 11
  • 2
    The answer is *always* an empty list, since its sum 0 is divisible by k and there's no shorter one. – Kelly Bundy Dec 29 '22 at 23:14
  • it has to be continuous – Nathan Dec 29 '22 at 23:42
  • @Nathan a somewhat-established convention is that ["substring" implies contiguous, and "subsequence" does not imply contiguous](https://math.stackexchange.com/questions/1237097/difference-subsequences-and-substrings). (Also note the word is contiguous, not continuous). – Stef Dec 30 '22 at 07:27
  • @Stef I think "subarray" refers to contiguous parts of arrays and "substring" refers to contiguous parts of strings. – Dave Dec 30 '22 at 17:41
  • @Dave and I think if you say "subarray", people will ask you "is it constrained to be contiguous or not?" whereas if you say "substring", they'll know. "subsequence" comes from sequences in the math sense, and "substring" comes from strings in the computer science sense, but they both apply to arrays. The point is that subsequence is unambiguously defined in math, and substring is unambiguously defined in computer science, so there is no ambiguity with this vocabulary. "subarray" is defined nowhere and is therefore ambiguous. – Stef Dec 30 '22 at 19:00

1 Answers1

3

Track the cumulative sums mod k in a map, with the cum_sums mod k as keys and the most recent index as values. Prior to updating the map for each index, first check if that key already exists. If it does, you have a contiguous subsequence divisible by k, and can calculate the length from the indices. Keep track of the min length.

Ruby code

def f(arr, k)
  h = Hash.new
  h[0] = -1 # to handle the case where the first r elts are divisible by k.
  min_len = Float::INFINITY
  cum_sum_mod_k = 0
  arr.each_with_index do |val, i|
    cum_sum_mod_k += val
    cum_sum_mod_k %= k
    if h.key?(cum_sum_mod_k)
      cur_len = i - h[cum_sum_mod_k]
      min_len = cur_len if cur_len < min_len
    end
    h[cum_sum_mod_k] = i
  end
  return min_len
end
Dave
  • 7,460
  • 3
  • 26
  • 39
  • Minor extra bookkeeping is easy to add if you want to return the relevant indices instead of the min length. – Dave Dec 30 '22 at 17:38