MiddleCodeOccasionalNot answered yet
Find a unique element in a container in one pass
Return the first element that appears exactly once in a generic container, or "no result" if every element repeats.
Requirements:
(For the special case "all duplicates appear exactly twice", a single XOR pass with O(1) space also exists.)
- O(n) time. Build counts in a single scan, then return the first count==1.
- Use
std::optionalfor the "might not exist" return. - Be honest about passes: a second scan to find the entry is a second pass.
template<typename Container>
std::optional<typename Container::value_type>
findFirstUnique(const Container& c) {
// your code here
}Write the implementation.
For integers where each duplicate appears exactly twice, XOR all values: a^a=0 leaves only the unique one — O(n) time, O(1) space. In the general case, build an unordered_map<T,int> of counts in one pass, then return the entry with count==1.
- ✗Claiming 'one pass' when the second scan of the map/set is actually a second pass
- ✗Using a sorted approach — requires two passes or sorting (O(n log n))
- ✗Not clarifying the problem constraints before choosing the algorithm
- →How would you find the first non-repeating character in a string in one pass?
- →What if elements can appear any number of times and you need the one with odd count?
Contents
Task
Find the first element that appears exactly once in a container.
Key points
- True one-pass with XOR works only when exactly one element has odd count.
- Hash-map counting is the general solution: O(n) time, O(n) space.
std::optionalis the idiomatic "might not exist" return type in C++17.
Contents
