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.
It's a bit depressing to see that the highest voted answer is very inefficient (traversing the array twice) and even doesn't make the best use of sets. Even more depressing to see that as the recommended solution from the challenge setter.
Create two empty sets. For each array element, if it isn't in the first one, add it to the first - otherwise, add it to the second.
The difference between the two will be the captain's room.
I know this is a toy challenge, but coders should always be thinking about how often they traverse a collection. Especially when the efficient solution is also simpler than the twice-traversal math-game solution.
Note: The set-based solution can be significantly faster than the math-game solution - details are discussed in my conversations with Tigran and Harikrishnand. It's harder to avoid loading the entire data set into memory, though, because this challenge puts all the input on a single line. It can be done, but that requires extra work to create your own input function that lazily iterates over the input from sys.stdin, rather than use the builtin input function.
The Captain's Room
You are viewing a single comment's thread. Return to all comments →
It's a bit depressing to see that the highest voted answer is very inefficient (traversing the array twice) and even doesn't make the best use of sets. Even more depressing to see that as the recommended solution from the challenge setter.
Create two empty sets. For each array element, if it isn't in the first one, add it to the first - otherwise, add it to the second.
The difference between the two will be the captain's room.
I know this is a toy challenge, but coders should always be thinking about how often they traverse a collection. Especially when the efficient solution is also simpler than the twice-traversal math-game solution.
Note: The set-based solution can be significantly faster than the math-game solution - details are discussed in my conversations with Tigran and Harikrishnand. It's harder to avoid loading the entire data set into memory, though, because this challenge puts all the input on a single line. It can be done, but that requires extra work to create your own input function that lazily iterates over the input from sys.stdin, rather than use the builtin input function.