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.
- Divisible Sum Pairs
- Discussions
Divisible Sum Pairs
Divisible Sum Pairs
Sort by
recency
|
186 Discussions
|
Please Login in order to post a comment
O(n) solution in Golang
This solution in Typescript uses a map to achieve O(n) time and space complexity in a single pass.
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.
Java 15
Little bit optimized option with usage of hash map of modulos: