Hacker News new | past | comments | ask | show | jobs | submit login

Wait... don't the two solutions have the same time complexity?

The bitwise XOR approach should depend on the maximum size of the numbers (say k) along with the length of the array (say n) as O(nk), and just using radix sort on the array will take time O(nk) too.

If you assume that bitwise XOR is constant time, that implies that the numbers in the array are bounded by a constant, and therefore Radix sort can sort the array in O(c.n) = O(n). In either case, they have the same running time.




Good point, but no - XOR is clearly better. It is simpler and its constant factor is less than the constant of a Radix sort.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: