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.
Python3, below solution uses a complement dictionary in order to get the runtime to be O(n), as it traverses the array once to generate the complement dictionary, then at most traverses the complement dictionary, which is at most O(n) in size, to get the answer. Space complexity is also O(n), as we have to store the complement dictionary, which is at most O(n), as well as two constants. Tricky part for me was trying to figure how to avoid double counting the pairs, so decided to split the counting. Also used the combination in math modele for values with same complement, but if that isn't allowed in some interview questions, you could always just use break it down to it's mathematical formula itself.
Divisible Sum Pairs
You are viewing a single comment's thread. Return to all comments →
Python3, below solution uses a complement dictionary in order to get the runtime to be O(n), as it traverses the array once to generate the complement dictionary, then at most traverses the complement dictionary, which is at most O(n) in size, to get the answer. Space complexity is also O(n), as we have to store the complement dictionary, which is at most O(n), as well as two constants. Tricky part for me was trying to figure how to avoid double counting the pairs, so decided to split the counting. Also used the combination in math modele for values with same complement, but if that isn't allowed in some interview questions, you could always just use break it down to it's mathematical formula itself.