Divisible subarrays is not clear to me

#1

can you please explain how to approach this problem and also please include a dry run code please

#2

You are given an array of positive and/or negative integers and a value K . The task is to find count of all sub-arrays whose sum is divisible by K
arr {4, 5, 0, -2, -3, 1}
K = 5
Output : 7
{4, 5, 0, -2, -3, 1}
{5}
{5, 0}
{5, 0, -2, -3}
{0}
{0, -2, -3}
{-2, -3}

Approach

  • Make an auxiliary array of size k as Mod[k] . This array holds the count of each remainder we are getting after dividing cumulative sum till any index in arr[].
  • Now start calculating cumulative sum and simultaneously take it’s mod with K, whichever remainder we get increment count by 1 for remainder as index in Mod[] auxiliary array. Sub-array by each pair of positions with same value of ( cumSum % k) constitute a continuous range whose sum is divisible by K.
  • Now traverse Mod[] auxiliary array, for any Mod[i] > 1 we can choose any two pair of indices for sub-array by (Mod[i]*(Mod[i] – 1))/2 number of ways . Do the same for all remainders < k and sum up the result that will be the number all possible sub-arrays divisible by K.

If you want code, google the question, you will find it