Let's say I have an unsorted array of integers. Is it possible to determine if there exists a number in the array that appears only once with a time complexity of less than O(nlogn)? Sorting the array takes nlogn time so I'm wondering if it's possible without sorting. I don't need to return the element, only to determine that it exists.(adsbygoogle = window.adsbygoogle || []).push({});

I think that the answer is no. If it was possible than it'd also be possible to check if two sets are equal or not in less that nlogn time since you could simply connect the sets and check if there's a unique element. Does anyone know the best algorithm for checking if two sets are equal?

Thanks,

Daniel

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Checking for a unique element

Loading...

Similar Threads for Checking unique element |
---|

Python Removing a list element that repeats itself -- Solved |

Python Extract all the text between the repeated unique strings in a large file |

C/++/# Typically where are preconditions checked for methods? |

Reading matrix elements from a file in Fortran77 |

C/++/# How to check if a list of numbers is random? |

**Physics Forums | Science Articles, Homework Help, Discussion**