4

Write psuedocode to determine the number of pairs of values in an input file that are equal. If your first try is quadratic, think again and develop a linearithmic solution.

I found this question in a textbook and I'm not sure how to write this algorithm. My guess at first was to write it along the formula nC2 = (n(n+1))/2. Any help is appreciated.

Improve this question
2
  • 2
    Hint: what changes if you sort the values before? What is the running time order for sorting? Can you even do better utilizing a dictionary?
    – Doc Brown
    Sep 26, 2012 at 6:21
  • Its a confusingly worded question, is it asking for you to spot when a value is in a file twice, or is it asking you to spot pairs whose value match (so spotting if file has 109 and 2, but also 106 and 5)?
    – colinjack
    Jul 23, 2013 at 14:36

1 Answer 1

Reset to default
4

I don't want to give you the code but some hints. The first thing to pay attention is that the exercise is asking for a linearithmic solutions. This means that you algorithm may consume N log (N) time to execute where N is the number of entries (values in the file in your case).

So the basic structure of the algorithm needed seems to be one loop through all the entries and one binary search inside the loop. To do a binary search you need an ordered entry, so order it. At the end you algorithm may look something like:

  1. Order the file
  2. Loop through the file
  3. Binary read the file during the loop
  4. Check the current value in the loop and the result of the binary search
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.