CODEWITHSUNDEEP
algorithmprefix-sum
Nathan
Nathan

Reputation: 360

Finding the shortest contiguous subsequence of array for which the sum can be divided by K

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!

Upvotes: 3

Views: 242

Answers (1)

Dave
Dave

Reputation: 9085

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

Upvotes: 3

Related Questions