Suppose you’re working for the national bank in some country and you’re asked to
ID: 3119090 • Letter: S
Question
Suppose you’re working for the national bank in some country and you’re asked toinvestigate a potential case of counterfeiting. The bank has seized a very large collection of n paper bills, suspecting that some of them may be counterfeits. Genuine bills have a unique serial number intricately woven into the fabric. For a counterfeit bill, though, its embedded serial number will likely be the same as that of another bill. (We’re talking about good counterfeits here—the rest have already been weeded out by the bank.)
It’s very dicult to read the serial number by examining the fabric directly, but the bank has a high-tech machine that, given two bills, will examine them both and then output whether or not the serials numbers on the bills are the same or dierent.
Your question is the following: Among the collection of n bills, is there a subset ofmore than n/2 of them that all have the same serial number as each other? Assume that the only feasible thing you can do with the bills is to insert two of them into the machine to test if they have the same serial number. Give an algorithm thatrequires only O(n log n) invocations of the machine.
Hint: Divide the n bills into two (roughly equal) halves. Show that if there is a set of more than n/2 bills with the same serial number, then at least one of the two halves must contain more than (n/2)/2 of them.
Explanation / Answer
Use the following steps:
1) First sort the elements in increasing or decreasing order using any of the sorting techniques (quick sort/merge sort/heap sort). It will take O(n log n) time.
2) After that all the duplicate bills come together.
3) Then you just need to compare adjacent elements (pair) using the machine. It just takes O(n) time.
4) Run a counter with initial value 0 and whenever duplicate bill is found just increase the counter by 1.
Hence we will get no. of duplicate bills.
Time Complexity = O(n log n) + O(n) = O(n log n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.