We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
O(n) solution in C++, two passes through the array.
First pass, initialize a hashmap with the values mod the desired sum
Second pass, remove the current element from the hashmap and find the subtractive complement frequency in the hashmap, add that to the result.
Edge case: if the number mods to 0, we don't do any subtraction, we just want to know how many successive elements are also multiples of k. Also of note, we don't want to use the [] operator, since that will implicitly insert that mod into the hashmap with a freq of 0, so we use the count function.
Divisible Sum Pairs
You are viewing a single comment's thread. Return to all comments →
O(n) solution in C++, two passes through the array.
First pass, initialize a hashmap with the values mod the desired sum
Second pass, remove the current element from the hashmap and find the subtractive complement frequency in the hashmap, add that to the result.
Edge case: if the number mods to 0, we don't do any subtraction, we just want to know how many successive elements are also multiples of k. Also of note, we don't want to use the
[]
operator, since that will implicitly insert that mod into the hashmap with a freq of 0, so we use thecount
function.