Recent searches
Search options
Tuesday common C++ interview problem: Find the singular number.
Given a sorted array of integers as std::vector<int>, where all values are present twice except for one singular number, return the singular number.
Your solution must run in O(logn) and use O(1) memory.
Solve it yourself: https://compiler-explorer.com/z/q6GbnEK1Y
Solution: https://compiler-explorer.com/z/Pf9h4PdEG
@simontoth solution is to xor everything.
@aurisc4 That definitely wouldn't be log(n).
@simontoth don't do it linear. Xor each pair, loop until one itm is left :)
@aurisc4 That would actually be n*log(n).
@simontoth yeah, sorted is better with binary search indeed. On a big list.