tag:blogger.com,1999:blog-2597841815280998418.post8535613086627182334..comments2024-03-12T06:45:01.935+01:00Comments on This Thread: Couples and SingleMannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-2597841815280998418.post-53304964146138668272015-03-07T19:09:27.487+01:002015-03-07T19:09:27.487+01:00Oh, come on, anonymous. Writing in all caps is con...Oh, come on, anonymous. Writing in all caps is considered rude, don't you know?<br />And, please, read my answer to the first comment.Mannyhttps://www.blogger.com/profile/07393063644320426727noreply@blogger.comtag:blogger.com,1999:blog-2597841815280998418.post-66211806985500355062015-03-04T23:13:36.409+01:002015-03-04T23:13:36.409+01:00USE XOR!!USE XOR!!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2597841815280998418.post-58809846498099677162015-01-07T11:27:06.254+01:002015-01-07T11:27:06.254+01:00Nice try but no. Sorting can't cost you less t...Nice try but no. Sorting can't cost you less than a O(n lg n) execution time, and that would become the dominant operation in your algorithm. Insert and lookup in a hash table are expected to be constant time operations, so my proposal runs in linear time.Mannyhttps://www.blogger.com/profile/07393063644320426727noreply@blogger.comtag:blogger.com,1999:blog-2597841815280998418.post-37308372596950452252015-01-06T17:36:39.685+01:002015-01-06T17:36:39.685+01:00would it be faster to sort input and check if inp...would it be faster to sort input and check if input[i]==input[i+1] in a 2-step loop ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-2597841815280998418.post-74312581504553572292015-01-03T20:47:48.974+01:002015-01-03T20:47:48.974+01:00XOR-ing is a smarter solution, thank you for point...XOR-ing is a smarter solution, thank you for pointing it out. I am not so happy with it just for my lack of trust in input data. It works fine assuming that we actually have a bunch of pairs and just one single element. For more singles it returns some unexpected value.<br />Moreover, if you pay attention to the problem definition, you should see how it refers to relatively small vectors. In the Mannyhttps://www.blogger.com/profile/07393063644320426727noreply@blogger.comtag:blogger.com,1999:blog-2597841815280998418.post-78686344896085207702014-12-25T16:16:30.655+01:002014-12-25T16:16:30.655+01:00That solution is not suitable for large vectors. I...That solution is not suitable for large vectors. If you have enough RAM check it on the amount of data in the 1-2GB with values in the array, which first increase monotonically till the array middle, and then again increase monotonically(starting with the same value as in previous part) till the end.<br />Better solution is to xor all array elements - result is the required unique value [O(n) - Anonymousnoreply@blogger.com