C++ Educational Content Creator | 20 years of Software Engineering experience distilled into digestible daily posts
Tuesday common C++ interview problem: Find the duplicate value. Given an array of length n+1 that contains the integers 1..n with one duplicate, return the duplicate. Your solution should have O(n) time complexity and O(1) space complexity. Solve it yourself: https://lnkd.in/dXJp8yWv Solution: https://lnkd.in/dhEjWBiB #cpp #cplusplus #coding #programming #dailybiteofcpp
The solution seems magical but it works. My solution was: auto sum = std::accumulate(nums.begin(), nums.end(), 0); int target {(nums.size() * (nums.size()-1))/2}; return sum-target; My solution has same time and space complexity but might overflow for edge cases. A better solution could look at bit manipulation to find the solution without overflowing
I think we should find the sum of all the elements and subtract from it the predefined sum of n elements. For n=9 the predefined sum is 45. For the shown example sum of elements = 54. So 54-45=9.
Here is an attempt : ) , key being using XOR properties n^n = 0 and n^0=n https://godbolt.org/z/4Y84W9zbj
Since the numbers are 1...n we can easily use xor operation.
Software Engineer at Raptor Technologies
2yNice solution, I was thinking we could compute the sum of the n+1 integers then subtract n(n+1)/2 from it.